A digraph such that for each its vertex, vertices of the out-neighbourhood have different in-degrees and vertices of the in-neighbourhood have different out-degrees, will be called an HI-digraph. In this paper, we give a characterization of sequences of pairs of out- and in-degrees of HI-digraphs.

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.

A k-monocore graph is a graph which has its minimum degree and degeneracy both equal to k. Integer sequences that can be the degree sequence of some k-monocore graph are characterized as follows. A nonincreasing sequence of integers d0, . . . , dn is the degree sequence of some k-monocore graph G, 0 ≤ k ≤ n − 1, if and only if k ≤ di ≤ min {n − 1, k + n − i} and ⨊di = 2m, where m satisfies [...] ≤ m ≤ k ・ n − [...] .

The line graph of a graph $G$, denoted by $L\left(G\right)$, has $E\left(G\right)$ as its vertex set, where two vertices in $L\left(G\right)$ are adjacent if and only if the corresponding edges in $G$ have a vertex in common. For a graph $H$, define ${\overline{\sigma }}_2\left(H\right)=min\{d\left(u\right)+d\left(v\right):uv\in E\left(H\right)\}$. Let $H$ be a 2-connected claw-free simple graph of order $n$ with $\delta \left(H\right)\ge 3$. We show that, if ${\overline{\sigma }}_2\left(H\right)\ge \frac{1}{7}(2n-5)$ and $n$ is sufficiently large, then either $H$ is traceable or the Ryjáček’s closure $\mathrm{cl}\left(H\right)=L\left(G\right)$, where $G$ is an essentially $2$-edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10 which have...

A graph $G$ is degree-continuous if the degrees of every two adjacent vertices of $G$ differ by at most 1. A finite nonempty set $S$ of integers is convex if $k\in S$ for every integer $k$ with $min\left(S\right)\le k\le max\left(S\right)$. It is shown that for all integers $r>0$ and $s\ge 0$ and a convex set $S$ with $min\left(S\right)=r$ and $max\left(S\right)=r+s$, there exists a connected degree-continuous graph $G$ with the degree set $S$ and diameter $2s+2$. The minimum order of a degree-continuous graph with a prescribed degree set is studied. Furthermore, it is shown that for every graph $G$ and convex set $S$ of...

We study new equivalence relations in spatial graph theory. We consider natural generalizations of delta link-homotopy on links, which is an equivalence relation generated by delta moves on the same component and ambient isotopies. They are stronger than edge-homotopy and vertex-homotopy on spatial graphs which are natural generalizations of link-homotopy on links. Relationship to existing familiar equivalence relations on spatial graphs are stated, and several invariants are defined by using the...

A graph G of order n is called arbitrarily partitionable (AP for short) if, for every sequence (n1, . . . , nk) of positive integers with n1 + ⋯ + nk = n, there exists a partition (V1, . . . , Vk) of the vertex set V (G) such that Vi induces a connected subgraph of order ni for i = 1, . . . , k. In this paper we show that every connected graph G of order n ≥ 22 and with [...] ‖G‖ > (n−42)+12 $\left|\right|G\left|\right|>\left(n-42\right)+12$ edges is AP or belongs to few classes of exceptional graphs.