✦ LIBER ✦

Forbidden subgraphs and hamiitonian properties in the square of a connected graph

✍ Scribed by Ronald J. Gould; Michael S. Jacobson

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 331 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080117

No coin nor oath required. For personal study only.

✦ Synopsis

Various Hamiltonian-like properties are investigated in the squares of connected graphs free of some set of forbidden subgraphs. The star K,+ the subdivision graph of &, and the subdivision graph of K1,3 minus an endvertex play central roles. In particular, we show that connected graphs free of the subdivision graph of K,,3 minus an endvertex have vertex pancyclic squares.

In this article, all graphs are finite, undirected, without loops or multiple edges. Terms not defined here can be found in [I]. If U is a nonempty subset of the vertex set V ( G ) of a graph G . then the subgraph (U) of G induced by U is the graph with vertex set U and whose edge set consists of those edges of G incident with two elements of U. A graph is Harniltonian if it contains a cycle through all its vertices. A graph is vertex pancyclic if each of its vertices lies on a cycle of length e, for each e, 3 e 6 IV(G)l. The square of a graph G , denoted GZ, is that graph obtained from G by inserting an edge between any two vertices at distance 2 apart in

📜 SIMILAR VOLUMES

The square of a connected S(K1,3)-free g

The square of a connected S(K1,3)-free graph is vertex pancyclic

✍ George Hendry; Walter Vogler 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

We prove the conjecture of Gould and Jacobson that a connected S(K1,J free graph has a vertex pancyclic square. Since .S(K1,J is not vertex pancyclic, this result is best possible. ## Our notation generally follows that used in [l] . A graph G is Hamilroniun if it contains a cycle through all its

The minimum number of subgraphs in a gra

The minimum number of subgraphs in a graph and its complement

✍ Lane Clark 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB 👁 2 views

## Abstract For a graphb __F__ without isolated vertices, let __M__(__F__; __n__) denote the minimum number of monochromatic copies of __F__ in any 2‐coloring of the edges of __K__~__n__~. Burr and Rosta conjectured that when __F__ has order __t__, size __u__, and __a__ automorphisms. Independent

The multiplicity of 1-factors in the squ

The multiplicity of 1-factors in the square of a graph

✍ G. R. T. Hendry 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB 👁 1 views

Several authors have shown that if G is a connected graph of even order then its square G2 has a I-factor. We show that the square of any connected graph of order 2n has at least n I-factors and describe all the extremal graphs.

On the largest tree of given maximum deg

On the largest tree of given maximum degree in a connected graph

✍ Y. Caro; I. Krasikov; Y. Roditty 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 1 views

## Abstract We prove that every connected graph __G__ contains a tree __T__ of maximum degree at most __k__ that either spans __G__ or has order at least __k__δ(__G__) + 1, where δ(__G__) is the minimum degree of __G.__ This generalizes and unifies earlier results of Bermond [1] and Win [7]. We als

The existence of a 2-factor in K1, n-fre

The existence of a 2-factor in K1, n-free graphs with large connectivity and large edge-connectivity

✍ R. E. L. Aldred; Yoshimi Egawa; Jun Fujisawa; Katsuhiro Ota; Akira Saito 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

In this article, we study the existence of a 2-factor in a K 1,nfree graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K 1,n -free graph of even order has a 1-factor.

A Study of in Vitro Neutralization of He

A Study of in Vitro Neutralization of Heparin by Thiazine, Oxazine, Phenazine, and Other Dyes††The authors wish to thank the National Aniline Division of Allied Chemical and Dye Corporation and Dyestuffs Division of E. I. du Pont de Nemours & Company for supplying s with the various types of dyes used and for information concerning their structure and physical properties; Dr. M. Kuizenga of the Upjohn Co. for the sodium heparinate used; nd Dorothy Payne for the construction of the graphs.

✍ Haley, Thomas J. ;Stolarsky, Frances 📂 Article 📅 1950 🏛 Elsevier ⚖ 372 KB 👁 1 views