Geodesic
On 2-periodic graphs of a certain graph operator
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 1, pp. 13-30 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 K_m,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.
Keywords: graph operator, power and complement of a graph, Desarguesian finite projective geometry, decomposition of a complete bipartite graph, generalized hypercube 
@article{DMGT_2001_21_1_a1,
     author = {Havel, Ivan and Zelinka, Bohdan},
     title = {On 2-periodic graphs of a certain graph operator},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {13--30},
     year = {2001},
     volume = {21},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a1/}
}
TY  - JOUR
AU  - Havel, Ivan
AU  - Zelinka, Bohdan
TI  - On 2-periodic graphs of a certain graph operator
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 13
EP  - 30
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a1/
LA  - en
ID  - DMGT_2001_21_1_a1
ER  - 
%0 Journal Article
%A Havel, Ivan
%A Zelinka, Bohdan
%T On 2-periodic graphs of a certain graph operator
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 13-30
%V 21
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a1/
%G en
%F DMGT_2001_21_1_a1
Havel, Ivan; Zelinka, Bohdan. On 2-periodic graphs of a certain graph operator. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 1, pp. 13-30. http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a1/

[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.

[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.

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

[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.

[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.

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