Can I read On K-pairable Regular Graphs on EtoBox?

On K-pairable Regular Graphs by Zhongyuan Che; Zhibo Chen is a Computer Science article available to read on EtoBox.

What is On K-pairable Regular Graphs about?

Let k be a positive integer. A graph G is said to be k-pairable if its automorphism group contains an involution φ such that d(x, φ(x)) ≥ k for any vertex x of G. The pair length of a graph G, denoted as p(G), is the maximum for any positive integer k. Some new results have been obtained since these concepts were introduced by Chen [Z. Chen, On k-pairable graphs, Discrete Mathematics 287 (2004) 11-15]. In the present paper, we first introduce a new concept called strongly induced cycle and use it to give a condition for a graph G to have p(G) = k. Then we consider the class G(r, k) of prime graphs which are r-regular and have pair length k. For any integers r, k ≥ 2, except r = k = 2, we show that the set G(r, k) is not empty, determine the minimum order of a graph in G(r, k), and give a construction for such a graph with the minimum order. With this approach, we also obtain the minimum order of an r-regular graph with pair length k for any integers r, k ≥ 2. Finally, we post an open question for further research.

Who reads On K-pairable Regular Graphs?

Author

Zhongyuan Che; Zhibo Chen

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0012-365X)

Published

2010

Language

EN

Field

Computer Science (Physical Sciences)