Degree sequence and supereulerian graphs

A sequence d=(d₁,d₂,…,d_n) is graphic if there is a simple graph G with degree sequence d, and such a graph G is called a realization of d. A graphic sequence d is line-hamiltonian if d has a realization G such that L(G) is hamiltonian, and is supereulerian if d has a realization G with a spanning eulerian subgraph. In this paper, it is proved that a nonincreasing graphic sequence d=(d₁,d₂,…,d_n) has a supereulerian realization if and only if d_n≥2 and that d is line-hamiltonian if and only if either d₁=n−1, or ∑_di=1d_i≤∑_dj≥2(d_j−2).     

Unicyclic and bicyclic graphs having minimum degree distance

In this paper characterizations of connected unicyclic and bicyclic graphs in terms of the degree sequence, as well as the graphs in these classes minimal with respect to the degree distance are given.     

A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs

Let $G$ be a balanced bipartite graph of order $2n\ge 4$, and let ${\sigma }_{1,1}\left(G\right)$ be the minimum degree sum of two non-adjacent vertices in different partite sets of $G$. In 1963, Moon and Moser proved that if ${\sigma }_{1,1}\left(G\right)\ge n+1$, then $G$ is hamiltonian. In this note, we show that if $k$ is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly $k$ cycles for sufficiently large graphs. In order to prove this, we also give a ${\sigma }_{1,1}$ condition for the existence of $k$ vertex-disjoint alternating cycles with respect to a chosen perfect matching in $G$.     

The connectivity and minimum degree of circuit graphs of matroids

Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense.     

关于超欧拉图的一个注记

设G是无向无环的有限图 ,若G有一个生成子图是欧拉图 (Euler) ,则称G是超欧拉图 (Supereulerian) .本文不利用收缩方法 ,直接证明了 :当图G至多差一边有两棵边不相交的生成树时 ,G是超欧拉图或者G有割边 .     

A Note on degree antiregular graphs

This note proves a conjecture of Merris that the minimal value of entries of the doubly stochastic matrix of the degree antiregular graph E_n of order n ≥ 3 is equal to (l/2(n + l)).     

A Note on degree antiregular graphs

This note proves a conjecture of Merris that the minimal value of entries of the doubly stochastic matrix of the degree antiregular graph E_n of order n ≥ 3 is equal to (l/2(n + l)).     

Degree conditions and degree bounded trees

We give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A a vertex subset of G. We denote by σ_k(A) the minimum value of the degree sum in G of any k independent vertices in A and by w(G−A) the number of components in the induced subgraph G−A. Our main results are the following: (i) If σ_k(A)≥|V(G)|−1, then G contains a tree T with maximum degree at most k and A⊆V(T). (ii) If σ_k−w(G−A)(A)≥|A|−1, then G contains a spanning tree T such that d_T(x)≤k for every x∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263-267] and the degree conditions are sharp.     

A note on cycle spectra of line graphs

We show that line graphs G=L(H) with σ₂(G)≥7 contain cycles of all lengths k, 2rad(H)+1≤k≤c(G). This implies that every line graph of such a graph with 2rad(H)≥Δ(H) is subpancyclic, improving a recent result of Xiong and Li. The bound on σ₂(G) is best possible.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

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.     

Undirected simple connected graphs with minimum number of spanning trees

We show that for positive integers n, m with n(n−1)/2≥m≥n−1, the graph L_n,m having n vertices and m edges that consists of an (n−k)-clique and k−1 vertices of degree 1 has the fewest spanning trees among all connected graphs on n vertices and m edges. This proves Boesch’s conjecture [F.T. Boesch, A. Satyanarayana, C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004-2009].     

A note on the minimum total coloring of planar graphs

Graph coloring is an important tool in the study of optimization,computer science,network design,e.g.,file transferring in a computer network,pattern matching,computation of Hessians matrix and so on.In this paper,we consider one important coloring,vertex coloring of a total graph,which is also called total coloring.We consider a planar graph G with maximum degree Δ(G)≥8,and proved that if G contains no adjacent i,j-cycles with two chords for some i,j∈{5,6,7},then G is total-(Δ+1)-colorable.     

Properties of connected graphs having minimum degree distance

The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P₄, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K₁+(K_1,k+1∪(n−k−3)K₁).