Discussiones
Mathematicae Graph Theory 21(1) (2001) 13-30
DOI: https://doi.org/10.7151/dmgt.1130
ON 2-PERIODIC GRAPHS OF A CERTAIN GRAPH OPERATOR
Ivan Havel Mathematical Institute, Academy of Sciences of the
Czech Republic |
Bohdan Zelinka Technical University |
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
Close