✦ LIBER ✦

A note on n-extendable graphs

✍ Scribed by Qinglin Yu

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 249 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160408

No coin nor oath required. For personal study only.

✦ Synopsis

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 ϵ E(G). © 1992 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th

A note on graphs spanned by Eulerian gra

A note on graphs spanned by Eulerian graphs

✍ W. R. Pulleyblank 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 1 views

## Abstract We show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP‐complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at

N-extendability of symmetric graphs

✍ R. E. L. Aldred; D. A. Holton; Dingjun Lou 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 361 KB

## 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

A note on regular Ramsey graphs

✍ Noga Alon; Sonny Ben-Shimon; Michael Krivelevich 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 81 KB

## Abstract We prove that there is an absolute constant __C__>0 so that for every natural __n__ there exists a triangle‐free __regular__ graph with no independent set of size at least \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle