# On 2-periodic graphs of a certain graph operator

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 1, page 13-30
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIvan Havel, and Bohdan Zelinka. "On 2-periodic graphs of a certain graph operator." Discussiones Mathematicae Graph Theory 21.1 (2001): 13-30. <http://eudml.org/doc/270637>.

@article{IvanHavel2001,

abstract = {We deal with the graph operator $\overline\{Pow₂\}$ defined to be the complement of the square of a graph: $\overline\{Pow₂\}(G) = \overline\{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.},

author = {Ivan Havel, Bohdan Zelinka},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph operator; power and complement of a graph; Desarguesian finite projective geometry; decomposition of a complete bipartite graph; generalized hypercube; power of graphs; generalized hypercubes; decomposition of complete bipartite graphs},

language = {eng},

number = {1},

pages = {13-30},

title = {On 2-periodic graphs of a certain graph operator},

url = {http://eudml.org/doc/270637},

volume = {21},

year = {2001},

}

TY - JOUR

AU - Ivan Havel

AU - Bohdan Zelinka

TI - On 2-periodic graphs of a certain graph operator

JO - Discussiones Mathematicae Graph Theory

PY - 2001

VL - 21

IS - 1

SP - 13

EP - 30

AB - We deal with the graph operator $\overline{Pow₂}$ defined to be the complement of the square of a graph: $\overline{Pow₂}(G) = \overline{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.

LA - eng

KW - graph operator; power and complement of a graph; Desarguesian finite projective geometry; decomposition of a complete bipartite graph; generalized hypercube; power of graphs; generalized hypercubes; decomposition of complete bipartite graphs

UR - http://eudml.org/doc/270637

ER -

## References

top- [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. Zbl0464.05057
- [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. Zbl0719.05036
- [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. Zbl0772.05043
- [6] E. Prisner, Graph dynamics (Pitman Research Notes in Mathematics Series, 338, 1995).

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.