Advanced Search

Let $r\ge 3$, $n\ge r$ and $\pi =(d_1,d_2,...,d_n)$ be a non-increasing sequence of nonnegative integers. If $\pi$ has a realization $G$ with vertex set $V\left(G\right)=\{v_1,v_2,...,v_n\}$ such that $d_G\left(v_i\right)=d_i$ for $i=1,2,...,n$ and $v_1{v}_2\cdots v_r{v}_1$ is a cycle of length $r$ in $G$, then $\pi$ is said to be potentially $C_r^{\text{'}\text{'}}$-graphic. In this paper, we give a characterization for $\pi$ to be potentially $C_r^{\text{'}\text{'}}$-graphic.

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

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

For given a graph $H$, a graphic sequence $\pi =(d_1,d_2,...,d_n)$ is said to be potentially $H$-graphic if there is a realization of $\pi$ containing $H$ as a subgraph. In this paper, we characterize the potentially $(K_5-e)$-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence $\pi$ to be potentially $K_5$-graphic, where $K_r$ is a complete graph on $r$ vertices and $K_r-e$ is a graph obtained from $K_r$ by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for...

A graph $G$ is a $k$-tree if either $G$ is the complete graph on $k+1$ vertices, or $G$ has a vertex $v$ whose neighborhood is a clique of order $k$ and the graph obtained by removing $v$ from $G$ is also a $k$-tree. Clearly, a $k$-tree has at least $k+1$ vertices, and $G$ is a 1-tree (usual tree) if and only if it is a $1$-connected graph and has no $K_3$-minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of $k$-trees as follows: if $G$ is a graph with at least $k+1$ vertices, then $G$ is a $k$-tree if...

A nonincreasing sequence $\pi =(d_1,...,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. In this case, $G$ is referred to as a realization of $\pi$. Given two graphs $G_1$ and $G_2$, A. Busch et al. (2014) introduced the potential-Ramsey number of $G_1$ and $G_2$, denoted by $r_{\mathrm{pot}}(G_1,G_2)$, as the smallest nonnegative integer $m$ such that for every $m$-term graphic sequence $\pi$, there is a realization $G$ of $\pi$ with $G_1\subseteq G$ or with $G_2\subseteq \overline{G}$, where $\overline{G}$ is the complement of $G$. For $t\ge 2$ and $0\le k\le \lfloor \frac{t}{2}\rfloor$, let $K_t^{-k}$ be the graph obtained...

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