✦ LIBER ✦

N-extendability of symmetric graphs

✍ Scribed by R. E. L. Aldred; D. A. Holton; Dingjun Lou

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 361 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170213

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

It is proved that a cyclically (k − 1)(2__n__ − 1)‐edge‐connected edge transitive k‐regular graph with even order is n‐extendable, where k ≥ 3 and k − 1 ≥ n ≥ ⌈(k + 1)/2⌉. The bound of cyclic edge connectivity is sharp when k = 3. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

A note on n-extendable graphs

✍ Qinglin Yu 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract A graph __G__ having a perfect matching is called n‐__extendable__ if every matching of size __n__ of __G__ can be extended to a perfect matching. In this note, we show that if __G__ is an __n__‐extendable nonbipartite graph, then __G__ + __e__ is (__n__ ‐ 1)‐extendable for any edge e ϵ

Hamiltonian cycles in n-extendable graph

Hamiltonian cycles in n-extendable graphs

✍ Ken-ichi Kawarabayashi; Katsuhiro Ota; Akira Saito 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB

## Abstract A graph __G__ of order at least 2__n__+2 is said to be __n__‐extendable if __G__ has a perfect matching and every set of __n__ independent edges extends to a perfect matching in __G__. We prove that every pair of nonadjacent vertices __x__ and __y__ in a connected __n__‐extendable graph

Edge proximity conditions for extendabil

Edge proximity conditions for extendability in cubic bipartite graphs

✍ R. E. L. Aldred; Bill Jackson 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB

## Abstract We show that a set __M__ of __m__ edges in a cyclically (3__m__ − 2)‐edge‐connected cubic bipartite graph is contained in a 1‐factor whenever the edges in __M__ are pairwise distance at least __f__(__m__) apart, where © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 112–120, 2007

Extending Graph Colorings

✍ Michael O Albertson; Emily H Moore 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 172 KB

Suppose /(G)=r and P V(G). It is known that if the distance between any two vertices in P is at least 4, then any (r+1)-coloring of P extends to an (r+1)-coloring of all of G, but an r-coloring of P might not extend to an r-coloring of G. We show that if the distance between any two vertices in P is

Self-complementary symmetric graphs

✍ Hong Zhang 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB

## Abstract The class of self‐complementary symmetric graphs is characterized using the classification of finite simple group.

Totally symmetric colored graphs

✍ Mariusz Grech; Andrzej Kisielewicz 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

## Abstract In this paper we describe almost all edge‐colored complete graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. This generalizes the recent description of self‐complementary symmetric graphs by Peisert and gives examples of permu