Line-graphs of cubic graphs are normal

A graph is called normal if its vertex set can be covered by cliques Q₁,Q₂,…,Q_k and also by stable sets S₁,S₂,…,S_l, such that S_i∩Q_j≠∅ for every i,j. This notion is due to Körner, who introduced the class of normal graphs as an extension of the class of perfect graphs. Normality has also relevance in information theory. Here we prove, that the line graphs of cubic graphs are normal.     

Almost all cubic graphs are Hamiltonian

In a previous article the authors showed that at least 98.4% of large labelled cubic graphs are hamiltonian. In the present article, this is improved to 100% in the limit by asymptotic analysis of the variance of the number of Hamilton cycles with respect to populations of cubic graphs with fixed numbers of short odd cycles.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

Generalized petersen graphs which are cycle permutation graphs

A cycle permutation graph is obtained by taking two n-cycles each labeled 1, 2,…, n, along with the edges obtained by joining i in the first copy to α(i) in the second, where α ∈ S_n. A characterization of the intersection between cycle permutation graphs and the generalized Petersen graphs as defined by Watkins (J. Combin. Theory6 (1969), 152–164), is given.     

On diagonal cubic surfaces

We show that the affine surfacesx ³+y ³+c z ³=c, c Q, in the casesc2,c=2, contain precisely 2, respectively 4, polynomial parametric solutions corresponding to curves of arithmetic genus 0 on the surface.However, these surfaces contain infinitely many polynomial parametric solutions corresponding to curves of arithmetic genus greater than 0.The author wishes to acknowledge the receipt of a Summer Support Grant for the College of Liberal Arts, Arizona State University, while this note was being written.     

The Plateau-Douglas problem for nonorientable minimal surfaces

In this paper, the solution of the Plateau-Douglas problem is presented for nonorientable minimal surfaces of higher genus in Riemannian manifolds.     

On a construction of critical graphs which are not sensitive

Let ?(G) be theclosed-set lattice of a graphG. G issensitive if the following implication is always true for any graphG′: ?(G)??(G′)?(G)?G′G iscritical if ?(G)??(G-e) for anye inE(G) and ?(G)??(G+e) for anye in \(\left( {\bar G} \right)\) where \(\bar G\) is the complement ofG. Every sensitive graph is, a fortiori, critical. Is every critical graph sensitive? A negative answer to this question is given in this note.     

On disjoint matchings in cubic graphs

For $i=2,3$ and a cubic graph $G$ let ${\nu }_i\left(G\right)$ denote the maximum number of edges that can be covered by $i$ matchings. We show that ${\nu }_2\left(G\right)\ge \frac{4}{5}\left|V\left(G\right)\right|$ and ${\nu }_3\left(G\right)\ge \frac{7}{6}\left|V\left(G\right)\right|$. Moreover, it turns out that ${\nu }_2\left(G\right)\le \frac{\left|V\left(G\right)\right|+2{\nu }_3\left(G\right)}{4}$.     

On incidence choosability of cubic graphs

An incidence of a graph $G$ is a pair $(u,e)$ where $u$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $u$. Two incidences $(u,e)$ and $(v,f)$ of $G$ are adjacent whenever (i) $u=v$, or (ii) $e=f$, or (iii) $uv=e$ or $uv=f$. An incidence$k$-coloring of $G$ is a mapping from the set of incidences of $G$ to a set of $k$ colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a $(2,3)$-bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3.     

Optimal 1-planar graphs which triangulate other surfaces

We show that, for any given non-spherical orientable closed surface F², there exists an optimal 1-planar graph which can be embedded on F² as a triangulation. On the other hand, we prove that there does not exist any such graph for the nonorientable closed surfaces of genus at most 3.     

The graphs for which all strong orientations are hamiltonian

We show that the only nontrivial strongly orientable graphs for which every strong oreintation is Hamiltonian are complete graphs and cycles.     

Blocks and the nonorientable genus of graphs

Examples are given to show that the nonorientable genus of a graph is not additive over its blocks. A nonorientable analog for the Battle, Harary, Kodama, and Youngs Theorem is proved; this completely determines the nonorientable genus of a graph in terms of its blocks. It is also shown that one of the above counterexamples has the minimum possible order.     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.