PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 21 | 1 | 13-30
Tytuł artykułu

On 2-periodic graphs of a certain graph operator

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
21
Numer
1
Strony
13-30
Opis fizyczny
Daty
wydano
2001
otrzymano
1999-12-27
poprawiono
2000-10-19
Twórcy
autor
  • Mathematical Institute, Academy of Sciences of the Czech Republic, Zitná 25, 115 67 Prague 1, Czech Republic
  • Technical University, Voronezská 13, 461 17 Liberec, Czech Republic
Bibliografia
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1130
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.