PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2001 | 21 | 1 | 13-30
Tytuł artykułu

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

Autorzy
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.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
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
autor
• 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