✦ LIBER ✦

On the extremal number of edges in hamiltonian connected graphs

✍ Scribed by Tung-Yang Ho; Cheng-Kuan Lin; Jimmy J.M. Tan; D. Frank Hsu; Lih-Hsing Hsu

Publisher: Elsevier Science
Year: 2010
Tongue: English
Weight: 421 KB
Volume: 23
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2009.03.025

No coin nor oath required. For personal study only.

✦ Synopsis

a b s t r a c t Assume that n and δ are positive integers with 3 ≤ δ < n. Let hc(n, δ) be the minimum number of edges required to guarantee an n-vertex graph G with minimum degree δ(G) ≥ δ to be hamiltonian connected.

📜 SIMILAR VOLUMES

The Number of Removable Edges in 3-Conne

The Number of Removable Edges in 3-Connected Graphs

✍ Su Jianji 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 147 KB

An edge of a 3-connected graph G is said to be removable if G&e is a subdivision of a 3-connected graph. Holton et al. (1990) proved that every 3-connected graph of order at least five has at least W(|G| +10)Â6X removable edges. In this paper, we prove that every 3-connected graph of order at least

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.

The number of connected sparsely edged g

The number of connected sparsely edged graphs

✍ E. M. Wright 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 472 KB

## Abstract An (__n, q__) graph has __n__ labeled points, __q__ edges, and no loops or multiple edges. The number of connected (__n, q__) graphs is __f(n, q)__. Cayley proved that __f(n, n__^‐1^) = __n__^n−2^ and Renyi found a formula for __f(n, n)__. Here I develop two methods to calculate the exp

Some results on characterizing the edges

Some results on characterizing the edges of connected graphs with a given domination number

✍ Laura A. Sanchis 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 821 KB

A dominatin# set for a graph G = (V, E) is a subset of vertices V' c\_ V such that for all v • V-V' there exists some u• V' for which {v,u} •E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let mz(G, D) denote the nu

The number of connected sparsely edged g

The number of connected sparsely edged graphs. IV large nonseparable graphs

✍ E. M. Wright 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 306 KB

The number of nonseparable graphs on n labeled points and q lines is u(n, 9). In the second paper of this series an exact formula for u(n, n + k) was found for general n and successive (small) k. The method would give an asymptotic approximation for fixed k as n + 30. Here an asymptotic approximatio

On partitioning the edges of graphs into

On partitioning the edges of graphs into connected subgraphs

✍ M. Jünger; G. Reinelt; W. R. Pulleyblank 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 559 KB

For any positive integer s, an s-partition of a graph G = ( ! -( €I is a partition of E into El U E2 U U E k, where 14 = s for 1 I i 5 k -1 and 1 5 1 4 1 5 s and each €; induces a connected subgraph of G. We prove (i) if G is connected, then there exists a 2-partition, but not neces-(ii) if G is 2-e