Abstract. Let [Formula: see text] be a multigraph. The cover index [Formula: see text] of [Formula: see text] is the greatest integer [Formula: see text] for which there is a coloring of [Formula: see text] with [Formula: see text] colors such that each vertex of [Formula: see text] is incident with at least one edge of each color. Let [Formula: see text] be the minimum degree of [Formula: see text], and let [Formula: see text] be the codensity of [Formula: see text], defined by [Formula: see text], where [Formula: see text] is the set of all edges of [Formula: see text] with at least one end in [Formula: see text]. It is easy to see that [Formula: see text]. In 1978, Gupta proposed the following codensity conjecture: Every multigraph [Formula: see text] satisfies [Formula: see text], which is the dual version of the Goldberg–Seymour conjecture on edge-colorings of multigraphs. In this note, we prove that [Formula: see text] if [Formula: see text] is not integral and [Formula: see text] otherwise. We also show that this codensity conjecture implies another conjecture concerning the cover index made by Gupta in 1967.

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 $\Delta$-critical if $\chi'(G)=\Delta(G)+1$ and $\chi'(H)\le \Delta(G)$ for every proper subgraph $H$ of $G$, and $G$ is overfull if $|E(G)|>\Delta(G) \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$.

Carvalho, Lucchesi, and Murty [J. Combin. Theory Ser. B, 92 (2004), pp. 319--324, Theorem 3.5] presented a proof of a theorem of Reed and Wakabayashi that a brick G is nonsolid if and only if there exist two vertex-disjoint odd cycles C_1 and C_2 such that G-V(C_1 u̧p C_2) has a perfect matching. Consequently, every brick with no two vertex-disjoint odd cycles is solid. Recently, Lucchesi et al. [SIAM J. Discrete Math., 32 (2018), pp. 1478--1501] constructed infinite families of solid bricks containing two vertex-disjoint odd cycles. Noticing that none of these graphs is cubic, they conjectured that no cubic solid brick contains two vertex-disjoint odd cycles. In this note, we present an infinite family of graphs showing that this conjecture fails. We further show that the minimum counterexample is unique, which has 12 vertices.

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, Handbook of Combinatorics, Vol. 1, MIT Press, Cambridge, MA, 1995, pp. 3--110]. A Halin graph is a planar graph consisting of two edge-disjoint subgraphs: a spanning tree of at least four vertices and with no vertex of degree 2, and a cycle induced by 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 and pancyclic Halin subgraph $H$. In addition, for every nonhamiltonian cycle $C$ in $H$, there is a cycle $C'$ longer than $C$ such that $C'$ contains all vertices from $C$ and at most two more vertices not from $C$.

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, Lovász 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.

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, Lovász 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.

Bollobás 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 Verstraëte's result: A graph of sufficiently large order with minimum degree at least $2k$ contains $k$ vertex-disjoint cycles of the same length.

The well-known Chvátal--Erdös 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 independence number and the connectivity of $G$, respectively. Oberly and Sumner [J. Graph Theory, 3 (1979), pp. 351--356] have proved that every connected, locally connected claw-free graph of order at least three has a Hamiltonian cycle. We study the connection of these two theorems. For $x\in V(G)$, let $B(x)$ denote the subgraph of $G$ induced by the closed neighborhood of $x$. Then the theorem by Oberly and Sumner says that a connected graph $G$ of order at least three satisfying $\alpha(B(x))\le 2\le \kappa(B(x))$ for every vertex $x$ has a Hamiltonian cycle. The comparison of this theorem with the Chvátal--Erdös theorem leads us to suspect that the threshold 2 between $\alpha(B(x))$ and $\kappa(B(x))$ is not necessary. We say that $G$ satisfies the local Chvátal--Erdös condition if $\alpha(B(x))\le\kappa(B(x))$ holds for every vertex $x$ in $G$. The second author conjectured that if the order of a connected graph $G$ is at least three and satisfies the local Chvátal--Erdös condition, then $G$ has a Hamiltonian cycle. In this paper, we support this conjecture by proving that under this assumption, $G$ is $1$-tough and has a $2$-factor.

The complete area coverage problem in Wireless Sensor Networks (WSNs) has been extensively studied in the literature. However, many applications do not require complete coverage all the time. For such applications, one effective method to save energy and prolong network lifetime is to partially cover the area. This method for prolonging network lifetime recently attracts much attention. However, due to the hardness of verifying the coverage ratio, all the existing centralized or distributed but nonparallel algorithms for partial coverage have very high time complexities. In this work, we propose a framework which can transform almost any existing complete coverage algorithm to a partial coverage one with any coverage ratio by running a complete coverage algorithm to find full coverage sets with virtual radii and converting the coverage sets to partial coverage sets via adjusting sensing radii. Our framework can preserve the characteristics of the original algorithms and the conversion process has low time complexity. The framework also guarantees some degree of uniform partial coverage of the monitored area.

One of the fundamental problems involving DNA sequences is to find high density segments of certain widths, for example, those regions with intensive guanine and cytosine (GC). Formally, given a sequence, each element of which has a value and a width, the maximum-density segment problem asks for the segment with the maximum density while satisfying minimum and possibly maximum width constraints. While several linear-time sequential algorithms have emerged recently due to its primitive-like utility, to our knowledge, no nontrivial parallel algorithm has yet been proposed for this topical problem. In this paper, we propose an O(log2n)-time CREW PRAM algorithm using n processors to solve the generalized maximum-density problem, with a minimum width constraint and non-uniform widths. Besides, we describe an efficient implementation of the parallel algorithm on manycore GPUs (nVIDIA GeForce GTX 280), taking advantage of the full programmability of CUDA. This algorithm can process up to million-size sequence within a second using an nVIDIA GeForce GTX 280, thus demonstrating the practicality of this algorithm as a basic primitive for scientists. This may also indicate suitability of modern GPU architectures as implementation platform for certain PRAM algorithms.

The complete area coverage problem in wireless sensor networks (WSNs) where every point inside an area is covered by an active sensor has been extensively studied in the literature. However, there are many applications that do not always require complete coverage. For such applications, an effective method to save energy and prolong network lifetime is to partially cover the area. However, due to the hardness to verify the ratio of the covered area over the entire monitored area (coverage ratio), all the existing algorithms for partial coverage have very high time complexities (either centralized algorithms or distributed but non-parallel algorithms). Besides, all the existing algorithms are intentionally designed for partial coverage, thus they do not utilize the various exiting methods for the complete coverage problem. In this work, we propose a framework that can convert almost any existing algorithm for complete coverage to a one for partial coverage with any coverage ratio. Our framework can preserve the characteristics of the original algorithms and the conversion process has low time complexity. The framework also guarantees some degree of uniform partial coverage of the monitored area.

Let G be a graph and $\mathbb{K}$ be a field. We associate to G a projective toric variety $X_G$ over $\mathbb{K}$, the cut variety of the graph G. The cut ideal $I_G$ of the graph G is the ideal defining the cut variety. We show that, if G is a subgraph of a subdivision of a book or an outerplanar graph, then the minimal generators are quadrics. Furthermore, we describe the generators of the cut ideal of a subdivision of a book.

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(n 3 ) 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)$.

We prove that every 18-tough chordal graph has a Hamiltonian cycle. © 1998 John Wiley & Sons, Inc. Networks 31: 29–38, 1998