DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 13-30
DOI: 10.7151/dmgt.1130

ON 2-PERIODIC GRAPHS OF A CERTAIN GRAPH OPERATOR

Ivan Havel

Mathematical Institute, Academy of Sciences of the Czech Republic
Zitná 25, 115 67 Prague 1, Czech Republic

Bohdan Zelinka

Technical University
Voronezská 13, 461 17 Liberec, Czech Republic

e-mail: Bohdan.Zelinka@vslib.cz

Abstract

We deal with the graph operator [`(Pow2)] defined to be the complement of the square of a graph: [`(Pow2)](G) = [`(Pow2(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 G 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 G. We further show that all the incidence graphs of Desarguesian finite projective geometries belong to G and find infinitely many graphs also belonging to G among generalized hypercubes.

Keywords: graph operator, power and complement of a graph, Desarguesian finite projective geometry, decomposition of a complete bipartite graph, generalized hypercube.

2000 Mathematics Subject Classification: 05C38, 05C75.

References

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

Received 27 December 1999
Revised 19 October 2000