On 2-periodic graphs of a certain graph operator

Ivan Havel; Bohdan Zelinka

Discussiones Mathematicae Graph Theory (2001)

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

Abstract

top
We deal with the graph operator P o w ₂ ¯ defined to be the complement of the square of a graph: P o w ₂ ¯ ( G ) = P o w ₂ ( 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.

How to cite

top

Ivan 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. [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. [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. [3] M. Hall, Jr., Combinatorial Theory (Blaisdell Publishing Company, Waltham (Massachusetts) - Toronto - London 1967). 
  4. [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. [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. [6] E. Prisner, Graph dynamics (Pitman Research Notes in Mathematics Series, 338, 1995). 

NotesEmbed ?

top

You must be logged in to post comments.