A perfect independent set $I$ of a graph $G$ is defined to be an independent set with the property that any vertex not in $I$ has at least two neighbors in $I$. For a nonnegative integer $k$, a subset $I$ of the vertex set $V\left(G\right)$ of a graph $G$ is said to be $k$-independent, if $I$ is independent and every independent subset $I^{\text{'}}$ of $G$ with $|I^{\text{'}}|\ge |I|-(k-1)$ is a subset of $I$. A set $I$ of vertices of $G$ is a super $k$-independent set of $G$ if $I$ is $k$-independent in the graph $G[I,V(G)-I]$, where $G[I,V(G)-I]$ is the bipartite graph obtained from $G$ by deleting all edges...

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

Let $K_m-H$ be the graph obtained from $K_m$ by removing the edges set $E\left(H\right)$ of $H$ where $H$ is a subgraph of $K_m$. In this paper, we characterize the potentially $K_5-P_4$ and $K_5-Y_4$-graphic sequences where $Y_4$ is a tree on 5 vertices and 3 leaves.

A matrix $𝒜$ whose entries come from the set $\{+,-,0\}$ is called a sign pattern matrix, or sign pattern. A sign pattern is said to be potentially nilpotent if it has a nilpotent realization. In this paper, the characterization problem for some potentially nilpotent double star sign patterns is discussed. A class of double star sign patterns, denoted by $𝒟SSP(m,2)$, is introduced. We determine all potentially nilpotent sign patterns in $𝒟SSP(3,2)$ and $𝒟SSP(5,2)$, and prove that one sign pattern in $𝒟SSP(3,2)$ is potentially stable.