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 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).     

Planar bipartite biregular degree sequences

A pair of sequences of natural numbers is called planar if there exists a simple, bipartite, planar graph for which the given sequences are the degree sequences of its parts. For a pair to be planar, the sums of the sequences have to be equal and Euler’s inequality must be satisfied. Pairs that verify these two necessary conditions are called admissible. We prove that a pair of constant sequences is planar if and only if it is admissible (such pairs can be easily listed) and is different from $\left(3^5\right|3^5)$ and $\left(3^{25}\right|5^{15})$.     

A simple criterion on degree sequences of graphs

A finite sequence of nonnegative integers is called graphic if the terms in the sequence can be realized as the degrees of vertices of a finite simple graph. We present two new characterizations of graphic sequences. The first of these is similar to a result of Havel-Hakimi, and the second equivalent to a result of Erd?s & Gallai, thus providing a short proof of the latter result. We also show how some known results concerning degree sets and degree sequences follow from our results.     

Spectral results on Hamiltonian problem

Let $\alpha$ be a non-negative real number, and let $\Theta (G,\alpha )$ be the largest eigenvalue of $A\left(G\right)+\alpha D\left(G\right)$. Specially, $\Theta (G,0)$ and $\Theta (G,1)$ are called the spectral radius and signless Laplacian spectral radius of $G$, respectively. A graph $G$ is said to be Hamiltonian (traceable) if it contains a Hamiltonian cycle (path), and a graph $G$ is called Hamilton-connected if any two vertices are connected by a Hamiltonian path in $G$. The number of edges of $G$ is denoted by $e\left(G\right)$. Recently, the (signless Laplacian) spectral property of Hamiltonian (traceable, Hamilton-connected) graphs received much attention. In this paper, we shall give a general result for all these existed results. To do this, we first generalize the concept of Hamiltonian, traceable, and Hamilton-connected to $s$-suitable, and we secondly present a lower bound for $e\left(G\right)$ to confirm the existence of $s$-suitable graphs. Thirdly, when $0\le \alpha \le 1$, we obtain a lower bound for $\Theta (G,\alpha )$ to confirm the existence of $s$-suitable graphs. Consequently, our results generalize and improve all these existed results in this field, including the main results of Chen et al. (2018), Feng et al. (2017), Füredi et al. (2017), Ge et al. (2016), Li et al. (2016), Nikiforov et al. (2016), Wei et al. (2019) and Yu et al. (2013, 2014).     

A Rao-type characterization for a sequence to have a realization containing an arbitrary subgraph H

Let G be an arbitrary spanning subgraph of the complete graph Kr+1 on r+1 vertices and Kr+1-E(G) be the graph obtained from Kr+1 by deleting all edges of G.A non-increasing sequence π=(d1,d2,...,dn) of nonnegative integers is said to be potentially Kr+1-E(G)-graphic if there is a graph on n vertices that has π as its degree sequence and contains Kr+1-E(G) as a subgraph.In this paper,a characterization of π that is potentially Kr+1-E(G)-graphic is given,which is analogous to the Erdo s–Gallai characterization of graphic sequences using a system of inequalities.This is a solution to an open problem due to Lai and Hu.As a corollary,a characterization of π that is potentially Ks,tgraphic can also be obtained,where Ks,t is the complete bipartite graph with partite sets of size s and t.This is a solution to an open problem due to Li and Yin.     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

New families of graphs determined by their generalized spectrum

We construct infinite families of graphs that are determined by their generalized spectrum. This construction is based on new formulae for the determinant of the walk matrix of a graph. All graphs constructed here satisfy a certain extremal divisibility condition for the determinant of their walk matrix.     

Relations on generalized degree sequences

We study degree sequences for simplicial posets and polyhedral complexes, generalizing the well-studied graphical degree sequences. Here we extend the more common generalization of vertex-to-facet degree sequences by considering arbitrary face-to-flag degree sequences. In particular, these may be viewed as natural refinements of the flag f-vector of the poset. We investigate properties and relations of these generalized degree sequences, proving linear relations between flag degree sequences in terms of the composition of rank jumps of the flag. As a corollary, we recover an f-vector inequality on simplicial posets first shown by Stanley.     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

Definable E0 classes at arbitrary projective levels

Using a modification of the invariant Jensen forcing of [11], we define a model of ZFC, in which, for a given $n\ge 3$, there exists a lightface ${\Pi }_n^1$-set of reals, which is a ${\mathsf{E}}_0$-equivalence class, hence a countable set, and which does not contain any OD element, while every non-empty countable ${\Sigma }_n^1$-set of reals is constructible, hence contains only OD reals.     

Graphic sequences with a realization containing a complete multipartite subgraph

A nonincreasing sequence of nonnegative integers π=(d₁,d₂,…,d_n) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realizeπ. For a given graph H, a graphic sequence π is potentiallyH-graphic if there is some realization of π containing H as a (weak) subgraph. Let σ(π) denote the sum of the terms of π. For a graph H and n∈Z⁺, σ(H,n) is defined as the smallest even integer m so that every n-term graphic sequence π with σ(π)≥m is potentially H-graphic. Let denote the complete t partite graph such that each partite set has exactly s vertices. We show that and obtain the exact value of σ(K_j+K_s,s,n) for n sufficiently large. Consequently, we obtain the exact value of for n sufficiently large.     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.