A short proof of a theorem on degree sets of graphs

For a finite simple graph G, we denote the set of degrees of its vertices, known as its degree set, by D(G). Kapoor, Polimeni and Wall [Degree sets for graphs, Fund. Math. 95 (1977) 189-194] have determined the least number of vertices among graphs with a given degree set. We give a very short proof of this result.     

The convex hull of degree sequences of signed graphs

As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope P_n. In this paper, we show that P_n is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of P_n, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153].     

On the degree distance of a graph

If G is a connected graph with vertex set V, then the degree distance of G, D^′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].     

The degree distribution of the random multigraphs

In this paper, as a generalization of the binomial random graph model, we define the model of multigraphs as follows: let G(n; {p _k }) be the probability space of all the labelled loopless multigraphs with vertex set V = {υ ₁, υ ₂, …, υ _n }, in which the distribution of t_{vi ,vj} t_{v_i ,v_j } , the number of the edges between any two vertices υ _i and υ _j is

The realization graph of a degree sequence with majorization gap 1 is Hamiltonian

It is known that the degree sequences of threshold graphs are characterized by the property that they are not majorized strictly by any degree sequence. Consequently every degree sequence d can be transformed into a threshold sequence by repeated operations consisting of subtracting I from a degree and adding 1 to a larger or equal degree. The minimum number of these operations required to transform d into a threshold sequence is called the majorization gap of d. A realization of a degree sequence d of length n is a graph on the vertices 1, …, n, where the degree of vertex i is d_i. The realization graph %plane1D;4A2;(d) of a degree sequence d has as vertices the realizations of d, and two realizations are neighbors in %plane1D;4A2;(d) if one can be obtained from the other by deleting two existing edges [a, b], [c, d] and adding two new edges [a, d]; [b, c] for some distinct vertices a, b, c, d. It is known that %plane1D;4A2;(d) is connected. We show that if d has a majorization gap of 1, then %plane1D;4A2;(d) is Hamiltonian.     

The minimum degree distance of graphs of given order and size

In this note, we study the degree distance of a graph which is a degree analogue of the Wiener index. Given n and e, we determine the minimum degree distance of a connected graph of order n and size e.     

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 polytope of degree sequences of hypergraphs

Let D_n(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope D_n(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes D_n(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on D_n(2). Our main results concern the extreme points and facets of D_n(r). We characterize adjacency of extreme points of D_n(r) and, in the case r=2, determine the distance between two given vertices in the graph of D_n(2). We give a characterization of when a linear inequality determines a facet of D_n(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of D_n(2); find an explicit family of Erdös–Gallai type facets of D_n(r); and describe a simple lifting procedure that produces a facet of D_n+1(r) from one of D_n(r).     

A remark on degree sequences of multigraphs

A sequence {d ₁, d ₂, . . . , d _n } of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v ₁, v ₂, . . . , v _n such that the degree d(v _i ) of the vertex v _i equals d _i for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize sequences that are multigraphic in a similar way, Havel (Časopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler, Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow.     

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.     

On the degree of approximation of functions belonging to a Lipschitz class by Hausdorff means of its fourier series

In a recent paper Lal and Yadov [4] obtained a theorem on the degree of approximation for a function belonging to the Lipschitz class Lipα using the product of the Cesàro and Euler means of order one of its Fourier series. In this paper we extend this result to any regular Hausdorff matrix for the same class of functions.     

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.     

Modular filter convergence theorems for Urysohn integral operators and applications

We prove some versions of modular convergence theorems for nonlinear Urysohn-type integral operators with respect to filter convergence. We consider pointwise filter convergence of functions giving also some applications to linear and nonlinear Mellin operators. We show that our results are strict extensions of the classical ones.     

Efficient counting of degree sequences

We present formulas to count the set $D_0\left(n\right)$ of degree sequences of simple graphs of order $n$, the set $D\left(n\right)$ of degree sequences of those graphs with no isolated vertices, and the set $D_{k\text{\_}con}\left(n\right)$ of degree sequences of those graphs that are $k$-connected for fixed $k$. The formulas all use a function of Barnes and Savage and the associated dynamic programming algorithms all run in time polynomial in $n$ and are asymptotically faster than previous known algorithms for these problems. We also show that $\left|D\left(n\right)\right|$ and $\left|D_{1\text{\_}con}\left(n\right)\right|$ are asymptotically equivalent but $\left|D\left(n\right)\right|$ and $\left|D_0\left(n\right)\right|$ as well as $\left|D\left(n\right)\right|$ and $\left|D_{k\text{\_}con}\left(n\right)\right|$ with fixed $k\ge 2$ are asymptotically inequivalent. Finally, we explain why we are unable to obtain the absolute asymptotic orders of these functions from their formulas.     

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.     

On the degree elevation of Bernstein polynomial representation

The polynomials determined in the Bernstein (Bézier) basis enjoy considerable popularity in computer-aided design (CAD) applications. The common situation in these applications is, that polynomials given in the basis of degree n have to be represented in the basis of higher degree. The corresponding transformation algorithms are called algorithms for degree elevation of Bernstein polynomial representations. These algorithms are only then of practical importance if they do not require the ill-conditioned conversion between the Bernstein and the power basis. We discuss all the algorithms of this kind known in the literature and compare them to the new ones we establish. Some among the latter are better conditioned and not more expensive than the currently used ones. All these algorithms can be applied componentwise to vector-valued polynomial Bézier representations of curves or surfaces.     

Number of walks and degree powers in a graph

This note deals with the relationship between the total number of k-walks in a graph, and the sum of the k-th powers of its vertex degrees. In particular, it is shown that the the number of all k-walks is upper bounded by the sum of the k-th powers of the degrees.