ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Mathematicae Graph Theory 21(1) (2001) 13-30DOI: 10.7151/dmgt.1130
Mathematical Institute, Academy of Sciences of the
Zitná 25, 115 67 Prague 1, Czech Republic
Voronezská 13, 461 17 Liberec, Czech Republic
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  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.
Received 27 December 1999
Revised 19 October 2000