✦ LIBER ✦

Degree sum for a triangle in a graph

✍ Scribed by Genghua Fan

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 379 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120216

No coin nor oath required. For personal study only.

✦ Synopsis

Let %(n; e) denote the class of graphs on n vertices and e edges. Define f(n, e) = min max{C:=, d(u,):{u,, up, uJ} induces a triangle in G}, where the maximum is taken over all triangles in the graph G and the minimum is taken over all G in %(n; e). From Turan's theorem, f(n, e) = 0 if e 5 n 2 / 4 ; otherwise f(n,e) > 0. Bollobas and Erdos (11 asked to determine the function f(n, e) for e > n2/4. Edwards [3] proved that f(n, e) 2 6e/n for e I n 2 / 3 . In this paper, w e consider the remaining case, namely, n2/4 < e < n2/3. A construction described in 141 shows that f(n, e) < 4 f l e -2n + 5. We prove that f(n, e ) P 21 e/4n. In particular, f(n, InZ/ 41 + 1) > 21n/16, which improves a result of Erdos and Laskar (41 that f(n,Ln2/4J + 1) > (1 + ~) n for some positive constant E . Furthermore, if e P 0.26n2, we obtain a better result.

📜 SIMILAR VOLUMES

A degree sum condition for longest cycle

A degree sum condition for longest cycles in 3-connected graphs

✍ Tomoki Yamashita 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 1 views

## Abstract For a graph __G__, we denote by __d__~__G__~(__x__) and κ(__G__) the degree of a vertex __x__ in __G__ and the connectivity of __G__, respectively. In this article, we show that if __G__ is a 3‐connected graph of order __n__ such that __d__~__G__~(__x__) + __d__~__G__~(__y__) + __d__~__

Degree sums for edges and cycle lengths

Degree sums for edges and cycle lengths in graphs

✍ Brandt, Stephan; Veldman, Henk Jan 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 3 views

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference-the length of a longest cycle-of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length be

A Degree Sum Condition for the Existence

A Degree Sum Condition for the Existence of a Contractible Edge in a κ-Connected Graph

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 184 KB

It is known that a noncomplete }-connected graph of minimum degree of at least w 5} 4 x contains a }-contractible edge, i.e., an edge whose contraction yields again a }-connected graph. Here we prove the stronger statement that a noncomplete }-connected graph for which the sum of the degrees of any

A degree condition for the circumference

A degree condition for the circumference of a graph

✍ Nathaniel Dean; Pierre Fraisse 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 1 views

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let rn be any positive integer. Suppose G is a 2-connected graph with vertices x,, . . . , x, and edge set E that satisfies the proper

A Short Proof of a Theorem Concerning De

A Short Proof of a Theorem Concerning Degree Sums and Connectivity on Hamiltonian Graphs

✍ Bing Wei 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 74 KB

proved that if G is a 2-connected graph with n vertices such that d(u)+d(v)+d(w) n+} holds for any triple of independent vertices u, v, and w, then G is hamiltonian, where } is the vertex connectivity of G. In this note, we will give a short proof of the above result.

A sharp lower bound for the circumferenc

A sharp lower bound for the circumference of 1-tough graphs with large degree sums

✍ Vu Dinh Hoa 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB 👁 1 views

## Abstract We show that every 1‐tough graph __G__ on __n__ ≥ 3 vertices with σ~3~≧ __n__ has a cycle of length at least min{__n, n__ + (σ~3~/3 ) − α + 1}, where σ~3~ denotes the minimum value of the degree sum of any 3 pairwise nonadjacent vertices and α the cardinality of a miximum independent se