Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . . , [am, bm]) and L2 = ([c1, d1], . . . , [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2 ≥ . . . ≥ cn. We say that L = (L1; L2) is potentially Ks,t (resp. As,t)-bigraphic if there is a simple bipartite graph G with partite sets X = {x1, . . . , xm} and Y = {y1, . . . , yn} such that ai ≤ dG(xi) ≤ bi for 1 ≤ i ≤ m, ci ≤ dG(yi) ≤ di for...

Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.

The split graph $K_r+\overline{K_s}$ on $r+s$ vertices is denoted by $S_{r,s}$. A non-increasing sequence $\pi =(d_1,d_2,...,d_n)$ of nonnegative integers is said to be potentially $S_{r,s}$-graphic if there exists a realization of $\pi$ containing $S_{r,s}$ as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for $\pi$ to be potentially $S_{r,s}$-graphic. They are extensions of two theorems due to A. R. Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series...

The minimum orders of degree-continuous graphs with prescribed degree sets were investigated by Gimbel and Zhang, Czechoslovak Math. J. 51 (126) (2001), 163–171. The minimum orders were not completely determined in some cases. In this note, the exact values of the minimum orders for these cases are obtained by giving improved upper bounds.

The imbalance of an edge $e=\{u,v\}$ in a graph is defined as $i\left(e\right)=\left|d\right(u)-d(v\left)\right|$, where $d(·)$ is the vertex degree. The irregularity $I\left(G\right)$ of $G$ is then defined as the sum of imbalances over all edges of $G$. This concept was introduced by Albertson who proved that $I\left(G\right)\le 4n^3/27$ (where $n=\left|V\right(G\left)\right|$) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2008. Our bound involves the...

A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours such that adjacent vertices receive distinct colours. Such a k-colouring is called acyclic, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, every cycle in G has at least three distinct colours. Acyclic colourings were introduced by Gr¨unbaum in 1973, and since then have...

For a vertex v in a weighted graph G, idw(v) denotes the implicit weighted degree of v. In this paper, we obtain the following result: Let G be a 2-connected weighted graph which satisfies the following conditions: (a) The implicit weighted degree sum of any three independent vertices is at least t; (b) w(xz) = w(yz) for every vertex z ∈ N(x) ∩ N(y) with xy /∈ E(G); (c) In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains...

We compare the asymptotic growth of the order of the digraphs arising from a construction of Comellas and Fiol when applied to Faber-Moore digraphs versus plainly the Faber-Moore digraphs for the corresponding degree and diameter.

Let $K_{s,t}$ be the complete bipartite graph with partite sets $\{x_1,...,x_s\}$ and $\{y_1,...,y_t\}$. A split bipartite-graph on $(s+s^{\text{'}})+(t+t^{\text{'}})$ vertices, denoted by ${\mathrm{SB}}_{s+s^{\text{'}},t+t^{\text{'}}}$, is the graph obtained from $K_{s,t}$ by adding $s^{\text{'}}+t^{\text{'}}$ new vertices $x_{s+1},...,x_{s+s^{\text{'}}}$, $y_{t+1},...,y_{t+t^{\text{'}}}$ such that each of $x_{s+1},...,x_{s+s^{\text{'}}}$ is adjacent to each of $y_1,...,y_t$ and each of $y_{t+1},...,y_{t+t^{\text{'}}}$ is adjacent to each of $x_1,...,x_s$. Let $A$ and $B$ be nonincreasing lists of nonnegative integers, having lengths $m$ and $n$, respectively. The pair $(A;B)$ is potentially ${\mathrm{SB}}_{s+s^{\text{'}},t+t^{\text{'}}}$-bigraphic if there is a simple bipartite graph containing ${\mathrm{SB}}_{s+s^{\text{'}},t+t^{\text{'}}}$ (with $s+s^{\text{'}}$ vertices $x_1,...,x_{s+s^{\text{'}}}$ in the part of size $m$ and $t+t^{\text{'}}$ vertices...

Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that $d_i>i$ or $d_{n-i}\ge n-i$. We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.