✦ LIBER ✦

On k-complementing permutations of cyclically k-complementary graphs

✍ Scribed by Jose M. Bernaldez

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 163 KB
Volume: 151
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00082-t

No coin nor oath required. For personal study only.

✦ Synopsis

Let {Hi}i,2 ..... k be an isomorphic factorization of K. where k >/2 and k divides ½n(n -1). If there is a permutation fl on V(K.) such that fl: V(Ht)---~ V(Ht,.,) is an isomorphism for i = 1, 2 ..... k -1 where {Ht,}i = 1,2 ..... k is a rearrangement of {H~}i = 1,2 ..... k then a graph G of order n isomorphic to H~ is called a cyclically k-complementary graph. We call the aforementioned permutation fl a k-complementing permutation of a cyclically k-complementary graph.

The purpose of this paper is to present some properties of k-complementing permutations of the said graphs.

📜 SIMILAR VOLUMES

On cyclically K-complementary graphs

✍ Jose M. Bernaldez 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 313 KB

Let {HiL,.,,,. ,x be an isomorphic factorization of K,. If there is a permutation p on V(K.) such that /j': V(H,)+ V(H,+ ,) is an isomorphism for i= 1,2, , k-1, then a graph isomorphic to Hi is called a cyclically k-complementary graph. In this paper, some theorems are presented to prove the exist

Rao's conjecture on self-complementary g

Rao's conjecture on self-complementary graphs with K-factors

✍ Kiyoshi Ando 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

## Abstract Rao posed the following conjecture, “Let G be a self‐complementary graph of order __p__, π = (d~1~ … dp) be its degree sequence. Then G has a k‐factor if and only if π − k, = (d1 − k, … dP − k) is graphical.” We construct a family of counterexamples for this conjecture for every k ⩾ 3.

On the k-diameter of k-regular k-connect

On the k-diameter of k-regular k-connected graphs

✍ D. Frank Hsu; Tomasz Łuczak 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 391 KB

We study the k-diameter of k-regular k-connected graphs. Among other results, we show that every k-regular k-connected graph on n vertices has k-diameter at most n/2 and this upper bound cannot be improved when n = 4k -6 + i(2k -4). In particular, the maximal 3-diameter of 3-regular graphs with 2n v

On the k-index of graphs

✍ Juraj Bosák 📂 Article 📅 1971 🏛 Elsevier Science 🌐 English ⚖ 540 KB

Almtngt. Gi~ a ter~ph, p~tn every two vt~rticet which me 5t a dhtance tugate¢ than a fixed intelget k t>l) by a new path of lenltth k. Thus a laaph tranlfor:nati~n ts defined. The least number of itaslttior~ of tht, tr;m~l'ofmalion Such that the last it~rJfion does not change the graph. et called th

On K1,k-factorizations of a complete bip

On K1,k-factorizations of a complete bipartite graph

✍ Hong Wang 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 311 KB

We present a necessary condition for a complete bipartite graph K,., to be K,.,-factorizable and a sufficient condition for K,,, to have a K,,,-factorization whenever k is a prime number. These two conditions provide Ushio's necessary and sufficient condition for K,,, to have a K,,,-factorization.

On vertex k-partitions of certain infini

On vertex k-partitions of certain infinite graphs

✍ Douglas Cenzer; Edward Howorka 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 826 KB

Let G be an infinite graph; define de& G to be the least m such that any partition P of the vertex set of G into sets of uniformly bounded cardinality contains a set which is adjacent to at least m Other sets of the partition. If G is either a regular tree 01 a triangtiisr, sqzart or hexagonal plana