✦ LIBER ✦

On the maximum number of diagonals of a circuit in a graph

✍ Scribed by Ram Prakash Gupta; Jeff Kahn; Neil Robertson

Publisher: Elsevier Science
Year: 1980
Tongue: English
Weight: 612 KB
Volume: 32
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(80)90097-7

No coin nor oath required. For personal study only.

✦ Synopsis

G, let a(G?

maximum number k such that G contains a circuit with k Theorem. For any graph G with minimum valency n 2 3, a(G) z=:$(n + l)(n -2).

If the equality holds and :3 is connected, then either G is isomorphic to K,,, or G is separable and each of its terminal blocks is isomorphic to K,+,, or K,,+I with one edge subdivided.

📜 SIMILAR VOLUMES

The maximum number of diagonals of a cyc

The maximum number of diagonals of a cycle in a block and its extremal graphs

✍ Feng Tian; Wenan Zang 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 739 KB

Tian, F. and W. Zang, The maximum number of diagonals of a cycle in a block and its extremal graphs, Discrete Mathematics 89 (1991) 51-63. In this paper we show that if G is a 2-connected graph having minimum degree n such that IV(G)1 L 2n + 1, then there exists a cycle in G having more than n(n -2

On the maximum number of cycles in a pla

On the maximum number of cycles in a planar graph

✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib

On the Maximum Number of Independent Cyc

On the Maximum Number of Independent Cycles in a Bipartite Graph

✍ Hong Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 404 KB

Let G=(V 1 , V 2 ; E ) be a bipartite graph with |V 1 |= |V 2 | =n 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k+1. We show that if n>2k, then G contains k vertex-disjoint cycles. We also show that if n=2k, then G contains k&1 quadrilaterals and a path of orde

The number of edges in a maximum cycle—d

The number of edges in a maximum cycle—distributed graph

✍ Yongbing Shi 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 288 KB

Shi, Y., The number of edges in a maximum cycle-distributed graph, Discrete Mathematics 104 (1992) 205-209. Let f(n) (f\*(n)) be the maximum possible number of edges in a graph (2-connected simple graph) on n vertices in which no two cycles prove that, for every integer n > 3, f(n) 3 n + k + [i( [~(

The irredundance number and maximum degr

The irredundance number and maximum degree of a graph

✍ B. Bollobás; E.J. Cockayne 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 104 KB

A vertex x in a subset X of vertices of an undirected graph is redundant if its dosed neighborhood is contained in the union of closed neighborhoods of vertices of X-{x}. In the context of a communications network, this means that any vertex that may receive communications from X may also be irdorme

The maximum number of edges in a minimal

The maximum number of edges in a minimal graph of diameter 2

✍ Zoltán Füredi 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 717 KB

## Abstract A graph __g__ of diameter 2 is minimal if the deletion of any edge increases its diameter. Here the following conjecture of Murty and Simon is proved for __n__ < __n__~o~. If __g__ has __n__ vertices then it has at most __n__^2^/4 edges. The only extremum is the complete bipartite graph