✦ LIBER ✦

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

✍ Scribed by Feng Tian; Wenan Zang

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 739 KB
Volume: 89
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90399-m

No coin nor oath required. For personal study only.

✦ Synopsis

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) diagonals, unless G is K n,mr m >n or the Petersen graph. So the conjecture posed by Gupta, Kahn and Robertson is settled completely.

📜 SIMILAR VOLUMES

On the maximum number of diagonals of a

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

✍ Ram Prakash Gupta; Jeff Kahn; Neil Robertson 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 612 KB

## 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,+,

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

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( [~(

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 cycles in a hamilton graph

✍ Yongbing Shi 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 523 KB

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