✦ LIBER ✦

On independent cycles and edges in graphs

✍ Scribed by Thomas Andreae

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 339 KB
Volume: 149
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00275-n

No coin nor oath required. For personal study only.

✦ Synopsis

For integers k, s with 0 ~ ~~2 and n >~ 3~ -s. Justesen (1989) determined ex(n, k, 0) for all n >~ 3k and EX(n,k,O) for all n > (13k -4)/4, thereby settling a conjecture of Erdrs and P6sa; further EX (n,k,k) was determined by Erdrs and Gallai (n>~2k). In the present paper, by modifying the argument presented by Justesen, we determine EX(n,k,s) for all n,k,s (0~~2, n>~3k -s).~~

📜 SIMILAR VOLUMES

Spanning Cycles Through Specified Edges

Spanning Cycles Through Specified Edges in Bipartite Graphs

✍ Reza Zamani; Douglas B. West 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

P ósa proved that if G is an n-vertex graph in which any two nonadjacent vertices have degree-sum at least n+k, then G has a spanning cycle containing any specified family of disjoint paths with a total of k edges. We consider the analogous problem for a bipartite graph G with n vertices and parts o

Proof of a conjecture of Häggkvist on cy

Proof of a conjecture of Häggkvist on cycles and independent edges

✍ Kenneth A. Berman 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 196 KB

A graph G of order n is a ck-graph if for every pair of d~tinct, nonadlacenl veJtlces x and y' d(x)+d(y)>~n+k where d(v) denotes the degree of a vertex v In this paper, we prove the

On the maximum number of independent edg

On the maximum number of independent edges in cubic graphs

✍ Arthur M. Hobbs; Edward Schmeichel 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 146 KB

Let the reals be extended to include oo with o~ > r

Contractible edges in longest cycles in

Contractible edges in longest cycles in non-Hamiltonian graphs

✍ M.N. Ellingham; R.L. Hemminger; Kathryn E. Johnson 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 727 KB

An edge of a 3-connected graph is contractible if its contraction results in a graph which is still 3-connected. All 3-connected graphs with seven or more vertices are known to have at least three contractible edges on any longest cycle. Recently, it has been conjectured that any non-Hamiltonian 3-c

Independent edges in bipartite graphs ob

Independent edges in bipartite graphs obtained from orientations of graphs

✍ J. G. Gimbel; K. B. Reid 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 800 KB

## Abstract Given a digraph __D__ on vertices __v__~1~, __v__~2~, ⃛, __v__~__n__~, we can associate a bipartite graph __B(D)__ on vertices __s__~1~, __s__~2~, ⃛, __s__~__n__~, __t__~1~, __t__~2~, ⃛, __t__~__n__~, where __s__~__i__~__t__~__j__~ is an edge of __B(D)__ if (__v__~__i__~, __v__~__j__~)

Edge disjoint cycles in graphs

✍ Li Hao 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 419 KB