Search

Given a simple graph $G$, denote by $\Delta(G)$, $\delta(G)$, and $\chi'(G)$ the maximum degree, the minimum degree, and the chromatic index of $G$, respectively. We say $G$ is \emph{$\Delta$-critical} if $\chi'(G)=\Delta(G)+1$ and $\chi'(H)\le \Delta(G)$ for every proper subgraph $H$ of $G$; and $G$ is \emph{overfull} if $|E(G)|>\Delta \lfloor |V(G)|/2 \rfloor$. Since a maximum matching in $G$ can have size at most $\lfloor |V(G)|/2 \rfloor$, it follows that $\chi'(G) = \Delta(G) +1$ if $G$ is overfull. Conversely, let $G$ be a $\Delta$-critical graph. The well known overfull conjecture of Chetwynd and Hilton asserts that $G$ is overfull provided $\Delta(G) > |V(G)|/3$. In this paper, we show that any $\Delta$-critical graph $G$ is overfull if $\Delta(G) - 7\delta(G)/4\ge(3|V(G)|-17)/4$., Comment: One portion of arXiv:2005.12909 is incorporated into this paper. arXiv admin note: text overlap with arXiv:2004.00734, arXiv:2103.05171

Let $G$ be an $n$-vertex graph with $n\ge 3$. A classic result of Dirac from 1952 asserts that $G$ is hamiltonian if $\delta(G)\ge n/2$. Dirac's theorem is one of the most influential results in the study of hamiltonicity and by now there are many related known results\,(see, e.g., J. A. Bondy, Basic Graph Theory: Paths and Circuits, Chapter 1 in: {\it Handbook of Combinatorics Vol.1}). A {\it Halin graph} is a planar graph consisting of two edge-disjoint subgraphs: a spanning tree of at least 4 vertices and with no vertex of degree 2, and a cycle induced on the set of the leaves of the spanning tree. Halin graphs possess rich hamiltonicity properties such as being hamiltonian, hamiltonian connected, and almost pancyclic. As a continuous "generalization" of Dirac's theorem, in this paper, we show that there exists a positive integer $n_0$ such that any graph $G$ with $n\ge n_0$ vertices and $\delta(G)\ge (n+1)/2$ contains a spanning Halin subgraph. In particular, it contains a spanning Halin subgraph which is also pancyclic., Comment: 25 pages, 3 figures

A Halin graph is a plane graph constructed from a planar drawing of a tree by connecting all leaves of the tree with a cycle which passes around the boundary of the graph. The tree must have four or more vertices and no vertices of degree two. Halin graphs have many nice properties such as being Hamiltonian and remaining Hamiltonian after any single vertex deletion. In 1975, Lovasz and Plummer conjectured that every 4-connected plane triangulation contains a spanning Halin subgraph. We recently gave a negative answer to this conjecture. In this paper, we construct an infinite class of 5-connected plane triangulations without a spanning Halin subgraph. Our smallest example contains 512 vertices.

Bollobas and Thomason showed that a multigraph of order $n$ and size at least $n+c\,(c\ge 1)$ contains a cycle of length at most $2(\lfloor n/c\rfloor+1)\lfloor \log_2 2c\rfloor$. We show in this paper that a multigraph (with no loop) of order $n$ and minimum degree at least 5 contains a chorded cycle (a cycle with a chord) of length at most $300\log_2 n$. As an application of this result, we show that a graph of sufficiently large order with minimum degree at least $3k+8$ contains $k$ vertex-disjoint chorded cycles of the same length, which is analogous to Verstraete's result: A graph of sufficiently large order with minimum degree at least $2k$ contains $k$ vertex-disjoint cycles of the same length.

A \sl Halin graph is a simple plane graph consisting of a tree without degree 2 vertices and a cycle induced by the leaves of the tree. In 1975, Lovasz and Plummer conjectured that every 4-connected plane triangulation has a spanning Halin subgraph. In this paper, we construct an infinite family of counterexamples to the conjecture.

The well-known Chvatal--Erdos theorem states that every graph $G$ of order at least three with $\alpha(G)\le\kappa(G)$ has a Hamiltonian cycle, where $\alpha(G)$ and $\kappa(G)$ are the independenc...

Jackson and Wormald conjecture that if $G$ is a 3-connected $n$-vertex graph with maximum degree $d\ge 4$, then $G$ has a cycle of length $\Omega(n^{\log_{d-1}2})$. We show that this conjecture holds when $d-1$ is replaced by $\max\{64,4d+1\}$. Our proof implies a cubic algorithm for finding such a cycle.

A graph $G$ of order $n$ is pancyclic if it contains cycles of all lengths from 3 to $n$. A graph is called cycle extendable if for every cycle $C$ of less than $n$ vertices there is another cycle $C^*$ containing all vertices of $C$ plus a single new vertex. Clearly, every cycle extendable graph is pancyclic if it contains a triangle. Cycle extendability has been intensively studied for dense graphs while little is known for sparse graphs, even very special graphs. We show that all Hamiltonian interval graphs are cycle extendable. This supports a conjecture of Hendry that all Hamiltonian chordal graphs are cycle extendable.

Karger, Motwani, and Ramkumar Algorithmica, 18 (1997), pp. 82--98] have shown that there is no constant approximation algorithm to find a longest cycle in a Hamiltonian graph, and they conjectured that this is the case even for graphs with bounded degree. On the other hand, Feder, Motwani, and Subi [SIAM J. Comput., 31 (2002), pp. 1596--1607] have shown that there is a polynomial time algorithm for finding a cycle of length $n^{\log_32}$ in a 3-connected cubic n-vertex graph. In this paper, we show that if G is a 3-connected n-vertex graph with maximum degree at most d, then one can find, in O(n3) time, a cycle in G of length at least $\Omega(n^{\log_b2})$, where $b=2(d-1)^2+1$.

Given a graph G, the normalized Laplacian associated with the graph G, denoted ${\cal L}$(G), was introduced by F. R. K. Chung and has been intensively studied in the last 10 years. For a k-regular graph G, the normalized Laplacian ${\cal L}$ (G) and the standard Laplacian matrix L(G) satisfy L(G) = k {\cal L} (G), and hence they have the same eigenvectors and their eigenvalues are directly related. However, for an irregular graph G, ${\cal L} (G) and L(G) behave quite differently, and the normalized Laplacian seems to be more natural. In this paper, Cauchy interlacing-type properties of the normalized Laplacian are investigated, and the following result is established. Let G be a graph, and let H = G - e, where e is an edge of G. Let $\lambda_1\geq \lambda_2 \geq \cdots \geq \lambda_{n}=0$ be the eigenvalues of ${\cal L}(G)$, and let $\theta_1\geq \theta_2 \geq \cdots \geq \theta_{n}$ be the eigenvalues of ${\cal L}(H)$. Then, $\lambda_{k-1} \geq \theta_{k}\geq \lambda_{k+1}$ for each k = 1, 2, 3, \dots, n, where $\lambda_{0} =2$ and $\lambda_{n+1}=0$. Applications are given for eigenvalues of graphs obtained from special graphs by adding or deleting a few edges. A short proof is given of the result that $G$ is a graph with each component a nontrivial bipartite graph if and only if $2-\lambda$ is an eigenvalue of ${\cal L}(G)$ for each eigenvalue $\lambda$ of ${\cal L }(G)$.