In the article, the following problems connected with the edge clique coverings of graphs are investigated: the structure of graphs whose edges can be covered by cliques with only one way; the possibility of graph reducing with the order decrease not changing the edge clique covering structure; algorithms for construction of minimal edge clique coverings; the interrelation between isomorphisms of graphs and corresponding reduced graphs.
Download file
Counter downloads: 241
- Title Edge clique coverings of graphs
- Headline Edge clique coverings of graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(19)
- Date:
- DOI
Keywords
NP-complete problems, graph isomorphism, edge clique covering, graphs, NP-полные задачи, изоморфизм графов, кликовое покрытие рёбер, графы, покрытия графов кликамиAuthors
References
Харари Ф. Теория графов М.: Мир, 1973. 301с.
Cavers M. S. Clique partitions and coverings of graphs. Masters thesis, University of Waterloo, 2005. http://www.math.uwaterloo.ca/co/graduate-students/files/mmath/ Mike-Cavers.pdf
Gramm J., Guo J., Huffner F., and Niedermeier R. Data reduction, exact, and heuristic algorithms for clique cover // Proc. 8th Workshop on Algorithm Engineering and Experiments, Miami, Fl. January 21, 2006. P. 86-94.
Kou L.T., Stockmeyer L. J., and Wong C. K. Cliques with regard to keyword conflicts and intersection graphs // Comm. ACM. 1978. V.21. No. 2. P. 135-139.
Orlin J. Contentment in graph theory: covering graphs with cliques // Indagat. Math. 1977. No. 39. P. 406-424.
Edge clique coverings of graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 1(19).
Download full-text version
Download fileCounter downloads: 234