An official website of the United States government
The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. In this paper, we consider the family of graphs which contain no $$K_{s,t}$$-minor. We show that for any $$t\geq s \geq 2$$ and sufficiently large $$n$$, there is an integer $$\xi_{t}$$ such that the extremal $$n$$-vertex $$K_{s,t}$$-minor-free graph attaining the maximum spread is the graph obtained by joining a graph $$L$$ on $(s-1)$ vertices to the disjoint union of $$\lfloor \frac{2n+\xi_{t}}{3t}\rfloor$$ copies of $$K_t$$ and $$n-s+1 - t\lfloor \frac{2n+\xi_t}{3t}\rfloor$$ isolated vertices. Furthermore, we give an explicit formula for $$\xi_{t}$$ and an explicit description for the graph $$L$$ for $$t \geq \frac32(s-3) +\frac{4}{s-1}$$.
more »
« less
An Ore-Type Condition for Hamiltonicity in Tough Graphs and the Extremal Examples
Let $$G$$ be a $$t$$-tough graph on $$n\ge 3$$ vertices for some $t>0$. It was shown by Bauer et al. in 1995 that if the minimum degree of $$G$$ is greater than $$\frac{n}{t+1}-1$$, then $$G$$ is hamiltonian. In terms of Ore-type hamiltonicity conditions, the problem was only studied when $$t$$ is between 1 and 2, and recently the second author proved a general result. The result states that if the degree sum of any two nonadjacent vertices of $$G$$ is greater than $$\frac{2n}{t+1}+t-2$$, then $$G$$ is hamiltonian. It was conjectured in the same paper that the $+t$ in the bound $$\frac{2n}{t+1}+t-2$$ can be removed. Here we confirm the conjecture. The result generalizes the result by Bauer, Broersma, van den Heuvel, and Veldman. Furthermore, we characterize all $$t$$-tough graphs $$G$$ on $$n\ge 3$$ vertices for which $$\sigma_2(G) = \frac{2n}{t+1}-2$$ but $$G$$ is non-hamiltonian.
more »
« less
- Award ID(s):
- 2345869
- PAR ID:
- 10519423
- Publisher / Repository:
- The Electronic Journal of Combinatorics
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 31
- Issue:
- 1
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
ABSTRACT In 1956, Tutte proved the celebrated theorem that every 4‐connected planar graph is Hamiltonian. This result implies that every more than ‐tough planar graph on at least three vertices is Hamiltonian and so has a 2‐factor. Owens in 1999 constructed non‐Hamiltonian maximal planar graphs of toughness arbitrarily close to and asked whether there exists a maximal non‐Hamiltonian planar graph of toughness exactly . In fact, the graphs Owens constructed do not even contain a 2‐factor. Thus the toughness of exactly is the only case left in asking the existence of 2‐factors in tough planar graphs. This question was also asked by Bauer, Broersma, and Schmeichel in a survey. In this paper, we close this gap by constructing a maximal ‐tough plane graph with no 2‐factor, answering the question asked by Owens as well as by Bauer, Broersma, and Schmeichel.more » « less
-
Abstract We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any $$d$$ -regular graph on $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ deviates from $$\frac{n}{d+1}$$ by at most $$2$$ . The second is that every graph on $$n$$ vertices with minimum degree $$\delta$$ contains a spanning subgraph in which the number of vertices of each degree does not exceed $$\frac{n}{\delta +1}+2$$ . Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices $$n$$ . In particular we show that if $$d^3 \log n \leq o(n)$$ then every $$d$$ -regular graph with $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ is $$(1+o(1))\frac{n}{d+1}$$ . We also prove that any graph with $$n$$ vertices and minimum degree $$\delta$$ contains a spanning subgraph in which no degree is repeated more than $$(1+o(1))\frac{n}{\delta +1}+2$$ times.more » « less
-
Abstract Let $$\gamma(G)$$ and $${\gamma _ \circ }(G)$$ denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G is an n -vertex graph of minimum degree at least d , then $$\begin{equation}\gamma(G) \leq \frac{n}{d}(\log d + 1).\end{equation}$$ In this paper the main result is that if G is any n -vertex d -regular graph of girth at least five, then $$\begin{equation}\gamma_(G) \leq \frac{n}{d}(\log d + c)\end{equation}$$ for some constant c independent of d . This result is sharp in the sense that as $$d \rightarrow \infty$$ , almost all d -regular n -vertex graphs G of girth at least five have $$\begin{equation}\gamma_(G) \sim \frac{n}{d}\log d.\end{equation}$$ Furthermore, if G is a disjoint union of $${n}/{(2d)}$$ complete bipartite graphs $$K_{d,d}$$ , then $${\gamma_\circ}(G) = \frac{n}{2}$$ . We also prove that there are n -vertex graphs G of minimum degree d and whose maximum degree grows not much faster than d log d such that $${\gamma_\circ}(G) \sim {n}/{2}$$ as $$d \rightarrow \infty$$ . Therefore both the girth and regularity conditions are required for the main result.more » « less
-
We determine the minimum degree sum of two adjacent vertices that ensures a perfect matching in a 3-uniform hypergraph without isolated vertex. Suppose that $$H$$ is a 3-uniform hypergraph whose order $$n$$ is sufficiently large and divisible by $$3$$. If $$H$$ contains no isolated vertex and $$\deg(u)+\deg(v) > \frac{2}{3}n^2-\frac{8}{3}n+2$$ for any two vertices $$u$$ and $$v$$ that are contained in some edge of $$H$$, then $$H$$ contains a perfect matching. This bound is tight and the (unique) extremal hyergraph is a different \emph{space barrier} from the one for the corresponding Dirac problem.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.37236/12483
