The signless Laplacian spectral radius of graphs with given degree sequences

In this paper, we investigate the properties of the largest signless Laplacian spectral radius in the set of all simple connected graphs with a given degree sequence. These results are used to characterize the unicyclic graphs that have the largest signless Laplacian spectral radius for a given unicyclic graphic degree sequence. Moreover, all extremal unicyclic graphs having the largest signless Laplacian spectral radius are obtained in the sets of all unicyclic graphs of order n with a specified number of leaves or maximum degree or independence number or matching number.     

The visibility graph of congruent discs is Hamiltonian

We show that the visibility graph of a set of disjoint congruent discs in is Hamiltonian, as long as the discs are not all supported by the same line. The proof is constructive, and leads to efficient algorithms for obtaining a Hamilton circuit.     

The signless Laplacian spectral radius of bicyclic graphs with prescribed degree sequences

In this paper, we characterize all extremal connected bicyclic graphs with the largest signless Laplacian spectral radius in the set of all connected bicyclic graphs with prescribed degree sequences. Moreover, the signless Laplacian majorization theorem is proved to be true for connected bicyclic graphs. As corollaries, all extremal connected bicyclic graphs having the largest signless Laplacian spectral radius are obtained in the set of all connected bicyclic graphs of order n (resp. all connected bicyclic graphs with a specified number of pendant vertices, and all connected bicyclic graphs with given maximum degree).     

A Rao-type characterization for a sequence to have a realization containing a split graph

For a given graph H, a non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is said to be potentially H-graphic if there exists a realization of π containing H as a subgraph. The split graph on r+s vertices is denoted by S_r,s. In this paper, we give a Rao-type characterization for π to be potentially S_r,s-graphic. A simplification of this characterization is also presented.     

Hamiltonian properties of locally connected graphs with bounded vertex degree

We consider the existence of Hamiltonian cycles for the locally connected graphs with a bounded vertex degree. For a graph G, let Δ(G) and δ(G) denote the maximum and minimum vertex degrees, respectively. We explicitly describe all connected, locally connected graphs with Δ(G)?4. We show that every connected, locally connected graph with Δ(G)=5 and δ(G)?3 is fully cycle extendable which extends the results of Kikust [P.B. Kikust, The existence of the Hamiltonian circuit in a regular graph of degree 5, Latvian Math. Annual 16 (1975) 33-38] and Hendry [G.R.T. Hendry, A strengthening of Kikust’s theorem, J. Graph Theory 13 (1989) 257-260] on full cycle extendability of the connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for the locally connected graphs with Δ(G)?7 is NP-complete.     

Every 4-connected line graph of a quasi claw-free graph is hamiltonian connected

Let G be a graph. For u,vV(G) with dist_G(u,v)=2, denote J_G(u,v)={wN_G(u)∩N_G(v)|N_G(w)N_G(u)N_G(v){u,v}}. A graph G is called quasi claw-free if J_G(u,v)≠ for any u,vV(G) with dist_G(u,v)=2. In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. In this paper we show that every 4-connected line graph of a quasi claw-free graph is hamiltonian connected.     

The number of vertices of degree 5 in a contraction-critically 5-connected graph

An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V₅(G) denote the vertex set of a graph G and the set of degree 5 vertices of G, respectively. We prove that each contraction-critically 5-connected graph G has at least |V(G)|/2 vertices of degree 5. We also show that there is a sequence of contraction-critically 5-connected graphs {G_i} such that lim_i→∞|V₅(G_i)|/|V(G_i)|=1/2.     

The Hamiltonian index of graphs

The Hamiltonian index of a graph G is defined as

h(G)=min{m:L^m(G) is Hamiltonian}.     

Degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle

Let 1a<b be integers and G a Hamiltonian graph of order |G|(a+b)(2a+b)/b. Suppose that δ(G)a+2 and max{deg_G(x), deg_G(y)}a|G|/(a+b)+2 for each pair of nonadjacent vertices x and y in G. Then G has an [a,b]-factor which is edge-disjoint from a given Hamiltonian cycle. The lower bound on the degree condition is sharp. For the case of odd a=b, there exists a graph satisfying the conditions of the theorem but having no desired factor. As consequences, we have the degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle.     

Graphic sequences with a realization containing intersecting cliques

Let r≥ 1, k≥ 2 and Fm1 ,...,mki;r denote the most general definition of a friendship graph, that is, the graph of Kr+m1 , . . . , Kr+mk meeting in a common r set, where Kr+mi is the complete graph on r + mi vertices. Clearly, | Fm1 ,...,mki;r | = m1+ ··· + mk + r. Let σ(Fm1 ,...,mki;r , n) be the smallest even integer such that every n-term graphic sequence π = (d1, d2, . . . , dn) with term sum σ(π) = d1 + d2 + ··· + dn ≥σ(Fm1 ,...,mki;r,n) has a realization G containing Fm1 ,...,mki;r as a subgraph. In this paper, we determine σ(Fm1 ,...,mki;r,n) for n sufficiently large.     

The degree sequence of Fibonacci and Lucas cubes

The Fibonacci cube Γ_n is the subgraph of the n-cube induced by the binary strings that contain no two consecutive 1’s. The Lucas cube Λ_n is obtained from Γ_n by removing vertices that start and end with 1. It is proved that the number of vertices of degree k in Γ_n and Λ_n is and , respectively. Both results are obtained in two ways, since each of the approaches yields additional results on the degree sequences of these cubes. In particular, the number of vertices of high resp. low degree in Γ_n is expressed as a sum of few terms, and the generating functions are given from which the moments of the degree sequences of Γ_n and Λ_n are easily computed.     

Neighborhood degree lists of graphs

The neighborhood degree list (NDL) is a graph invariant that refines information given by the degree sequence and joint degree matrix of a graph and is useful in distinguishing graphs having the same degree sequence. We show that the space of realizations of an NDL is connected via a switching operation. We then determine the NDLs that have a unique realization by a labeled graph; the characterization ties these NDLs and their realizations to the threshold graphs and difference graphs.     

The average degree of a subcubic edge-chromatic critical graph

A graph is here called 3- critical if , and for every edge of . The 3-critical graphs include (the Petersen graph with a vertex deleted), and subcubic graphs that are Hajós joins of copies of . Building on a recent paper of Cranston and Rabern, it is proved here that if is 3-critical and not nor a Hajós join of two copies of , then has average degree at least ; this bound is sharp, as it is the average degree of a Hajós join of three copies of .