Loading...
Please wait, while we are loading the content...
Similar Documents
Edge clique covering sum of graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Davoodi, Akbar Javadi, Ramin Omoomi, Behnaz |
| Copyright Year | 2016 |
| Abstract | The edge clique cover sum number (resp. edge clique partition sum number) of a graph G, denoted by scc(G) (resp. scp(G)), is defined as the smallest integer k for which there exists a collection of complete subgraphs of G, covering (resp. partitioning) all edges of G such that the sum of sizes of the cliques is at most k. By definition, scc(G) $${\leqq}$$≦ scp(G). Also, it is known that for every graph G on n vertices, scp(G) $${\leqq n^{2}/2}$$≦n2/2. In this paper, among some other results, we improve this bound for scc(G). In particular, we prove 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) $${\leqq cnd\left\lceil\log \left(({n-1})/(d-1)\right)\right\rceil}$$≦cndlog(n-1)/(d-1), where c is a constant. Moreover, we conjecture that this bound is best possible up to a constant factor. Using a well-known result by Bollobás on set systems, we prove that this conjecture is true at least for d = 2. Finally, we give an interpretation of this conjecture as an interesting set system problem which can be viewed as a multipartite generalization of Bollobás’ two families theorem. |
| Starting Page | 82 |
| Ending Page | 91 |
| Page Count | 10 |
| File Format | PDF HTM / HTML |
| DOI | 10.1007/s10474-016-0586-1 |
| Volume Number | 149 |
| Alternate Webpage(s) | http://bomoomi.iut.ac.ir/sites/bomoomi.iut.ac.ir/files/file_pubwdet/edge_clique_covering_sum_of_graphs.pdf |
| Alternate Webpage(s) | https://doi.org/10.1007/s10474-016-0586-1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
