✦ LIBER ✦

The maximum number of edges in a graph with fixed edge-degree

✍ Scribed by R.J. Faudree; J. Sheehan

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 633 KB
Volume: 183
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00078-2

No coin nor oath required. For personal study only.

✦ Synopsis

Suppose that n i> 2t + 2 (t/> 17). Let G be a graph with n vertices such that its complement is connected and, for all distinct non-adjacent vertices u and v, there are at least t common neighbours. Then we prove that and

Furthermore, the results are sharp.

📜 SIMILAR VOLUMES

An upper bound on the number of edges of

An upper bound on the number of edges of edge-coloring critical graphs with high maximum degree

✍ Lian-ying Miao; Shi-you Pang; Jian-liang Wu 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 100 KB

In this paper, we prove that any edge-coloring critical graph G with maximum degree ¿ (11 + √ 49 -24 )=2, where 6 1, has the size at least 3(|V (G)| -) + 1 if 6 7 or if ¿ 8 and |V (G)| ¿ 2 --4 -( + 6)=( -6), where is the minimum degree of G. It generalizes a result of Sanders and Zhao.

Maximum number of edges in connected gra

Maximum number of edges in connected graphs with a given domination number

✍ Laura A. Sanchis 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 519 KB

Sanchis, L.A., Maximum number of edges in connected graphs with a given domination number, Discrete Mathematics 87 (1991) 65-72.

Acyclic edge coloring of graphs with max

Acyclic edge coloring of graphs with maximum degree 4

✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract An __acyclic__ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The __acyclic chromatic index__ of a graph is the minimum number __k__ such that there is an acyclic edge coloring using __k__ colors and is denoted by __a__′(__G__). It was conj

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 maximum number of edges in 2K2-free

The maximum number of edges in 2K2-free graphs of bounded degree

✍ F.R.K. Chung; A. Gyárfás; Z. Tuza; W.T. Trotter 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 481 KB

A graph is 2K,-free if it does not contain an independent pair of edges as an induced subgraph. We show that if G is 2K,-free and has maximum degree A(G) = D, then G has at most 5D2/4 edges if D is even. If D is odd, this bound can be improved to (5D\* -20 + 1)/4. The extremal graphs are unique.

The size of edge chromatic critical grap

The size of edge chromatic critical graphs with maximum degree 6

✍ Rong Luo; Lianying Miao; Yue Zhao 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB 👁 1 views

## Abstract In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph ${{G}} = ({{V}}, {{E}})$ with maximum degree $\Delta$, $|{{E}}| \geq {{{1}}\over {{2}}}\{(\Delta {{- 1}})|{{V}}| + {{3}}\}$. This conject