✦ LIBER ✦

The maximum size of graphs satisfying a degree condition

✍ Scribed by Yiping Qiu; Xiao Feng Jia

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 196 KB
Volume: 104
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90335-d

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a simple graph of order n without isolated vertices. If the integer h satisfies

In this note the maximum size of Sri(h)--graphs is determined. A result of Krol and Veldman on critically h-connected graphs follows as a corollary.

📜 SIMILAR VOLUMES

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

Sizes of graphs with induced subgraphs o

Sizes of graphs with induced subgraphs of large maximum degree

✍ Paul Erdős; Talmage James Reid; Richard Schelp; William Staton 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 249 KB

Graphs with n + k vertices in which every set of n +j vertices induce a subgraph of maximum degree at least n are considered. For j = 1 and for k fairly small compared to n, we determine the minimum number of edges in such graphs.

Relationships between total domination,

Relationships between total domination, order, size, and maximum degree of graphs

✍ Anders Yeo 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

## Abstract A total dominating set, __S__, in a graph, __G__, has the property that every vertex in __G__ is adjacent to a vertex in __S__. The total dominating number, γ~__t__~(__G__) of a graph __G__ is the size of a minimum total dominating set in __G__. Let __G__ be a graph with no component of

All nonhamiltonian tough graphs satisfyi

All nonhamiltonian tough graphs satisfying a 3-degree sum and fan-type conditions

✍ W. Frydrych 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 819 KB

Frydrych, W., All nonhamiltonian tough graphs satisfying a 3-degree sum and Fan-type conditions, Discrete Mathematics 121 (1993) 93-104. It is shown that if G is a l-tough nonhamiltonian graph on even number vertices n>4 such that d(x)+d(y)+d(z)>n for every triple of mutually distinct and nonadjace

A characterization of panconnected graph

A characterization of panconnected graphs satisfying a local ore-type condition

✍ Asratian, A. S.; H�ggkvist, R.; Sarkisian, G. V. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 1 views

It is well known that a graph G of orderp 2 3 is Hamilton-connected if d(u) +d(v) 2 p + 1 for each pair of nonadjacent vertices u and w. In this paper we consider connected graphs G of order at least 3 for which where N ( z ) denote the neighborhood of a vertex z. We prove that a graph G satisfying

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