Skip to main content
SUPERVISOR
Gholamreza Omidi,Behnaz Omoomi,Ramin Gavadi jourtani
غلامرضا امیدی اردلی (استاد مشاور) بهناز عمومی (استاد راهنما) رامین جوادی جورتانی (استاد راهنما)
 
STUDENT
Akbar Davoodi Zavareh
اکبر داودی زواره

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Doctor of Philosophy (PhD)
YEAR
1391
Let $ G $ be a simple graph. A family of cliques of $ G $ is called an (edge) clique covering for $ G $ if every edge of $ G $ belongs to at least one member of the family. A clique covering in which each edge belongs to exactly one clique, is called a \extit{clique partition}. The minimum size of a clique covering of $G$ is called the \extit{clique cover number} of $G$ and is denoted by $\\cc(G)$. Similarly, the \extit{clique partition number} of $G$, denoted by $ \\cp(G) $, is defined as the minimum number of cliques in a clique partition of $ G $. The subject of clique covering has bee widely studied in recent decades. First time, Erd\\H os et al. in \\cite{enerdos66} presented a close relationship between the clique covering and the set intersection representation. Also, they proved that the clique partition number of a graph on $ n $ vertices cannot exceed ${n^2}/{4} $ (known as Erd\\H os-Goodman-P{\\'o}sa theorem). The connections of clique covering and other combinatorial objects have been explored in the literature (see e.g. \\cite{enWallis87, enRees86}). For a survey of the Also a number of different variants of the clique cover number have been proposed. In this thesis, two clique covering parameters, namely {\extit{edge clique cover sum number}} and {\extit{local clique cover number}} have been studied. The {\\it edge clique cover sum number} (or the {\\it sigma clique cover number}) of a graph $G$, denoted by $\\scc(G)$, is defined as the smallest integer $k$ for which there exists a collection of complete subgraphs of $G$, covering all edges of $G$ such that the sum of cardinality of the cliques is at most $k$. Similarly, the {\\it sigma clique partition number} of $ G $ is defined as the smallest integer $ k $ for which there exists a clique partition of $ G $ such that the sum of sizes of the cliques is at most $k$. By definition, $\\scc(G)\\leq \\scp(G)$. It was conjectured by Katona and Tarj\\' an and proved independently by Chung \\cite{enchung81}, Gy\\H ori and Kostochka \\cite{engyori80} and Kahn \\cite{enkahn81} that every graph on $n$ vertices admits a clique partition such that the sum of number of vertices in these cliques is at most $\\lfloor n^2/2\\rfloor$, i.e. $ \\scp(G)\\leq \\lfloor n^2/2\\rfloor$. This can be considered as a generalization of Erd\\H os-Goodman-P{\\'o}sa theorem. The thesis begins by considering the four well known graph theory concepts, namely, the \extit{set intersection representation}, the \extit{Kneser representation}, the \extit{line hypergraph} and the \extit{clique covering} in Chapter \\ref{chp:chapter1}. The conceptual relations of these concepts and their corresponding parameters are illustrated as well. In Chapter \\ref{chp:chap2}, among some other results, the known bound for $\\scc(G)$ is improved. In particular, it is proved that if $G$ is a graph on $n$ vertices with no isolated vertex and the maximum degree of the complement of $G$ is $ d-1 $, for some integer $d$, then $ \\scc(G)\\leq cnd\\lceil\\log \\left(({n-1})/{(d-1)}\\right)\\rceil$, where $c$ is a constant. Moreover, it is conjectured that this bound is best possible up to a constant factor. Using a well-known result by Bollob{\\'a}s on set systems, it is shown that this conjecture is true for $ d=2 $. Finally, an interpretation of this conjecture as an interesting set system problem is given which can be viewed as a multipartite generalization of Bollob{\\'a}s' two families theorem as follows. Let $d\\geq 2$, $t\\geq 1$ and $\\mathcal{F}= \\{(A^1_i, A^2_i,\\ldots, A^d_i) \\ :\\ 1\\leq i\\leq t \\} $ such that $ A^j_i $ is a set of size $ k_{ij} $ and $ A^j_i \\cap A^{j'}_{i'}=\\emptyset $ if and only if $ i= i' $ and $ j\eq j' $. Then, there exists a function $ f $ and a constant $ c $, such that for every $ t\\geq f(d) $, \\[\\sum_{i,j}{k_{ij}} \\geq c d^2 t\\log t. \\] In Chapter \\ref{chp:chapter3}, we investigate an analogous problem of minimizing the sum of block sizes in a pairwise balanced design, where there are some constraints on the size of one block or the size of the largest block. For every positive integers $n,m$, where $m\\leq n$, let $\\mathscr{S}(n,m)$ be the smallest integer $s$ for which there exists a PBD on $n$ points whose largest block has size $m$ and the sum of its block sizes is equal to $s$. Also, let $\\mathscr{S}'(n,m)$ be the smallest integer $s$ for which there exists a PBD on $n$ points which has a block of size $m$ and the sum of it block sizes is equal to $s$. In this chapter, some lower bounds for $\\mathscr{S}(n,m)$ and $\\mathscr{S}'(n,m)$ are obtained. . <
منظور از یک خوشه در گراف G ، یک زیرگراف کامل از گراف G است. یک پوشش خوشه‌ای برای E(G)خانواده‌ای از خوشه‌ها مانند C است، به طوری که هر یال از G به حداقل یک خوشه از C تعلق داشته باشد. اگر در یک پوشش خوشه‌ای هر یال از گراف دقیقاً در یک عضو از C ظاهر شود، به آن یک افراز خوشه‌ای گفته می‌شود. در یک پوشش (افراز) خوشه‌ای تعداد خوشه‌های شامل یک رأس ظرفیت آن رأس نامیده می‌شود. پارامتری که در این رساله مورد مطالعه قرار گرفته است کمترین مقدار مجموع ظرفیت‌ رئوس در بین همه پوشش‌های (افرازهای) خوشه‌ای یک گراف است و عدد پوشش (افراز) خوشه‌ای جمعی نامیده می‌شود. در این رساله ضمن مطالعه این پارامترها و یافتن نتایج گوناگون، کران‌هایی برای عدد پوشش (افراز) خوشه‌ای جمعی برحسب پارامترهای مختلف گراف ارائه شده است. علاوه بر این، در راستای بررسی محکم بودن کران‌های به دست آمده، این پارامترها برای برخی از گراف‌های شناخته شده خاص محاسبه شده است.

ارتقاء امنیت وب با وف بومی