On 2-periodic graphs of a certain graph operator
Ivan Havel ; Bohdan Zelinka
Discussiones Mathematicae Graph Theory, Tome 21 (2001), p. 13-30 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

We deal with the graph operator Pow₂¯ defined to be the complement of the square of a graph: Pow₂¯(G)=Pow₂(G)¯. Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph Km,n can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective geometries belong to and find infinitely many graphs also belonging to among generalized hypercubes.

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:270637 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1130,
     author = {Ivan Havel and Bohdan Zelinka},
     title = {On 2-periodic graphs of a certain graph operator},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {21},
     year = {2001},
     pages = {13-30},
     zbl = {0990.05107},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1130}
}

Ivan Havel; Bohdan Zelinka. On 2-periodic graphs of a certain graph operator. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 13-30. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1130/

[000] [1] J. Akiyama, H. Era and G. Exoo, Further results on graph equations for line graphs and n'th power graphs, Discrete Math. 34 (1981) 209-218, doi: 10.1016/0012-365X(81)90001-7. | Zbl 0464.05057

[001] [2] T. Dvorák, I. Havel, J-M. Laborde and P. Liebl, Generalized hypercubes and graph embedding with dilation, Rostocker Mathematisches Kolloquium 39 (1990) 13-20. | Zbl 0719.05036

[002] [3] M. Hall, Jr., Combinatorial Theory (Blaisdell Publishing Company, Waltham (Massachusetts) - Toronto - London 1967).

[003] [4] F. Harary, Four difficult unsolved problems in graph theory, in: M. Fiedler ed., Recent Advances in Graph Theory, Proc. Second Czech. Symp. Graph Theory, Prague, 1974 (Academia, Praha, 1975) 249-256.

[004] [5] Ch. Payan, On the chromatic number of cube-like graphs, Discrete Math. 103 (1992) 271-277, doi: 10.1016/0012-365X(92)90319-B. | Zbl 0772.05043

[005] [6] E. Prisner, Graph dynamics (Pitman Research Notes in Mathematics Series, 338, 1995).