𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A result on extendibility in the powers of graphs

✍ Scribed by Kara Walcher Shavo

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
309 KB
Volume
56
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a graph on p vertices. Then for a positive integer n, G is said to be n‐extendible if (i) n < p/2, (ii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G. The purpose of this article is to show that if G^2__k__^ is n‐extendible, for some kβ€‰βˆˆβ€‰β„•, then so is G^2__k__+1^, where G^q^ is the graph with the same vertex set as G and in which two vertices u and v are adjacent if and only if d~G~(u,v) ≀ q. We will also show that if G^k^ is 1‐extendible then so is G^k+1^. Β© 2007 Wiley Periodicals, Inc. J Graph Theory 56: 1–22, 2007

πŸ“œ SIMILAR VOLUMES

Various results on the toughness of grap
Various results on the toughness of graphs
✍ Broersma, Hajo; Engbers, Erik; Trommel, Huib πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 90 KB πŸ‘ 2 views

Let G be a graph and let t Υ† 0 be a real number. Then, We discuss how the toughness of (spanning) subgraphs of G and related graphs depends on (G), we give some sufficient degree conditions implying that (G) Υ† t, and we study which subdivisions of 2-connected graphs have minimally 2-tough squares.

On the hamiltonian path graph of a graph
On the hamiltonian path graph of a graph
✍ George R. T. Hendry πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 491 KB πŸ‘ 1 views

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and u are adjacent if and only if F contains a hamiltonian u -u path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian grap

On the Distribution of Powers in Finite
On the Distribution of Powers in Finite Fields
✍ Arne Winterhof πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 298 KB

Using a special ordering +x , 2 , x N D \ , of the elements of an arbitrary finite field and the term semicyclic consecutive elements, defined in Winterhof (''On the Distribution of Squares in Finite Fields,'' Bericht 96/20, Institute fu¨r Mathematik, Technische Universita¨t Braunschweig), some dist

On the eulericity of a graph
On the eulericity of a graph
✍ K. R. Matthews πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 200 KB

## Abstract The eulericity Ο΅(__G__) of a bridgeless graph __G__ is defined as the least number of eulerian subgraphs of __G__ which together cover the lines of __G__. A 1–1 correspondence is shown to exist between the __k__‐tuples of eulerian subgraphs of __G__ and the proper flows (mod2^__k__^) on