On n-hamiltonian graphs

A graph G of order p ? 3 is called n-hamiltonian, 0 ? n ? p ? 3, if the removal of any m vertices, 0 ? m ? n, results in a hamiltonian graph. A graph G of order p ? 3 is defined to be n-hamiltonian, ?p ? n ? 1, if there exists ?n or fewer pairwise disjoint paths in G which collectively span G. Various conditions in terms of n and the degrees of the vertices of a graph are shown to be sufficient for the graph to be n-hamiltonian for all possible values of n. It is also shown that if G is a graph of order p ? 3 and $\text{K}\text{(G) ? β(G) + n (?p ? n ? p ? 3)}$, then G is n-hamiltonian.     

On k-minimally n-edge-connected graphs

A graph is k-minimal with respect to some parameter if the removal of any j edges j<k reduces the value of that parameter by j. For k = 1 this concept is well-known; we consider multiple minimality, that is, k ? 2. We characterize all graphs which are multiply minimal with respect to connectivity or edge-connectivity. We also show that there are essentially no diagraphs which are multiply minimal with respect to diconnectivity or edge-diconnectivity. In addition, we investigate basic properties and multiple minimality for a variant of edge-connectivity which we call edge^m-connectivity.     

On n-skein isomorphisms of graphs

H. Whitney [Amer. J. Math.54 (1932), 150–168] proved that edge isomorphisms between connected graphs with at least five vertices are induced by isomorphisms and that circuit isomorphisms between 3-connected graphs are induced by isomorphisms. R. Halin and H. A. Jung [J. London Math. Soc.42 (1967), 254–256] generalized these results by showing that for n ≥ 2, n-skein isomorphisms between (n+1)-connected graphs are induced by isomorphisms. In this paper we show that for n ≥ 2, n-skein isomorphisms between 3-connected graphs having (n+1)-skeins are induced by isomorphisms.     

Further results on graph equations for line graphs and n-th power graphs

We present solutions of seven graph equations involving the line graph, complement and n-th power operations. One such equation $\text{L(G)}{}^{\mathrm{n}}\text{=}\text{G}\text{?}$ generalizes a result of M. Aigner. In addition, some comments are made about graphs satisfying $\text{G}{}^{\mathrm{n}}\text{=}\text{G}\text{?}$.     

On the 1-factors of n-connected graphs

L. W. Beineke and M. D. Plummer have recently proved [1] that every n-connected graph with a 1-factor has at least n different 1-factors. The main purpose of this paper is to prove that every n-connected graph with a 1-factor has at least as many as n(n − 2)(n − 4) … 4 · 2, (or: n(n − 2)(n − 4) … 5 · 3) 1-factors. The main lemma used is: if a 2-connected graph G has a 1-factor, then G contains a vertex V (and even two such vertices), such that each edge of G, incident to V, belongs to some 1-factor of G.     

Characterization of n-path graphs and of graphs having nth root

We characterize connected graphs and digraphs having an nth root and so generalize results by A. Mukhopadhyay and D. P. Geller, respectively. We then define the n-path graph of a graph and characterize those graphs which are n-path graphs. This extends recent results by B. Devadas Acharya and M. N. Vartak. The corresponding problem for digraphs is also considered.     

Characterizations of n-connected and n-line connected graphs

The following two theorems are proved: (1) A graph G with at least n + 1 points, n ≥ 2, is n-connected if and only if for each set S of n distinct points of G and for each two point subset T of S there is a cycle of G that contains the points of T and avoids the points of S ? T. (2) A graph G with at least n + 1 lines, n ≥ 2, with no isolated points is n-line connected if and only if for each set S of n distinct lines of G and for each two line subset T of S there is a circuit of G that contains the lines of T and avoids the lines of S ? T.     

On a property of the class of n-colorable graphs

An obvious lower bound on the chromatic number of a graph is the largest possible number of points in a complete subgraph. A sufficient condition is presented for these numbers to be equal. From this is derived a necessary and sufficient condition, believed to be new, for a graph to be n-colorable.     

n-Tuple colorings and associated graphs

The n-tuple graph coloring, which assigns to each vertex n colors, is defined together with its respective chromatic number x_n. It is proved that these numbers satisfy the inequality x_n ≥ 2 + x_n?1, and that equality holds only for bipartite graphs. Graphs $\text{G}{}_{\mathrm{n}}{}^{\mathrm{m}}$ are defined which play the same role for the n-tuple coloring that K_m plays for the conventional coloring. The chromatic numbers of various classes of graphs are also calculated.     

On pancyclic line graphs

In this paper, we give a best possible Ore-like condition for a graph so that its line graph is pancyclic or vertex pancyclic.     

On subpancyclic line graphs

We give a best possible Dirac-like condition for a graph G so that its line graph L(G) is subpancyclic, i.e., L(G) contains a cycle of length l for each l between 3 and the circumference of G. The result verifies the conjecture posed by Xiong (Pancyclic results in hamiltonian line graphs, in: Combinatorics and Graph Theory '95, vol. 2, Proceedings of the Summer School and International Conference on Combinatorics, World Scientific). © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 67–74, 1998     

On line perfect graphs

Line-perfect graphs have been defined by L.E. Trotter as graphs whose line-graphs are perfect. They are characterized by the property of having no elementary odd cycle of size larger than 3. L.E. Trotter showed constructively that the maximum cardinality of a set of mutually non-adjacent edges (matching) is equal to the minimum cardinality of a collection of sets of mutually adjacent edges which cover all edges.The purpose of this note is to give an algorithmic proof that the chromatic index of these graphs is equal to the maximum cardinality of a set of mutually adjacent edges.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

n-point sets and graphs of functions

We prove that, for every n?2, there exists an n-point set (a plane set which hits every line in exactly n points) that is homeomorphic to the graph of a function from R to R; for n?4, there exist both 0-dimensional and 1-dimensional examples. This raises the question (which we do not answer) of whether n-point sets for different n's could be homeomorphic.     

Counting perfect matchings in n-extendable graphs

The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least ⌈(n+1)!/4[q-p-(n-1)(2Δ-3)+4]⌉ different perfect matchings, where Δ is the maximum degree of a vertex in G.     

On the spectral radius of bicyclic graphs with n vertices and diameter d

Bicyclic graphs are connected graphs in which the number of edges equals the number of vertices plus one. In this paper we determine the graph with the largest spectral radius among all bicyclic graphs with n vertices and diameter d. As an application, we give first three graphs among all bicyclic graphs on n vertices, ordered according to their spectral radii in decreasing order.     

On circuits and pancyclic line graphs

Clark proved that L(G) is hamiltonian if G is a connected graph of order n ≥ 6 such that deg u + deg v ≥ n – 1 – p(n) for every edge uv of G, where p(n) = 0 if n is even and p(n) = 1 if n is odd. Here it is shown that the bound n – 1 – p(n) can be decreased to (2n + 1)/3 if every bridge of G is incident with a vertex of degree 1, which is a necessary condition for hamiltonicity of L(G). Moreover, the conclusion that L(G) is hamiltonian can be strengthened to the conclusion that L(G) is pancyclic. Lesniak-Foster and Williamson proved that G contains a spanning closed trail if |V(G)| = n ≥ 6, δ(G) ≥ 2 and deg u + deg v ≥ n – 1 for every pair of nonadjacent vertices u and v. The bound n – 1 can be decreased to (2n + 3)/3 if G is connected and bridgeless, which is necessary for G to have a spanning closed trail.