Let \(G\) be a graph. A vertex subversion strategy of \(G\), \(S\), is a set of vertices in \(G\) whose closed neighborhood is deleted from \(G\). The survival-subgraph is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), \(\mathrm{VNI}(G)\), is defined to be \(\mathrm{VNI}(G) = \min_{S\subseteq V(G)} \{|S| + w(G/S)\}\), where \(S\) is any vertex subversion strategy of \(G\), and \(w(G/S)\) is the maximum order of the components of \(G/S\). In this paper, we discuss the relationship between the vertex-neighbor-integrity and some well-known graphic parameters.

We construct, for all positive integers \(u\) and \(v\) with \(u \leq v\), a decomposition of \(K_v – K_u\) (the complete graph on \(v\) vertices with a hole of size \(u\)) into the maximum possible number of edge-disjoint triangles.

In this paper, we deal with the convex generators of a graph \(G = (V(G), E(G))\). A convex generator being a minimal set whose convex hull is \(V(G)\), we show that it is included in the “boundary” of \(G\). Then we show that the “boundary” of a polymino’s graph, or more precisely the seaweed’s “boundary”, enjoys some nice properties which permit us to prove that for such a graph \(G\), the minimal size of a convex generator is equal to the maximal number of hanging vertices of a tree \(T\), obtained from \(G\) by a sequence of generator-preserving contractions.

We address questions of Chartrand et al. about \(k\)-stratified graphs and distance graphs. A \(k\)-stratified graph \(G\) is a graph whose vertices have been partitioned into \(k\) distinct color classes, or strata. An underlying graph \(G’\) is obtained by ignoring the colors of \(G\). We prove that for every pair of positive integers \(k\) and \(l\), there exists a pair of \(2\)-stratified graphs with exactly \(k\) greatest common stratified subgraphs such that their underlying graphs have exactly \(l\) greatest common subgraphs.

A distance graph \(D(A)\) has vertices from some set \(A\) of \(0-1\) sequences of a fixed length and fixed weight. Two vertices are adjacent if one of the corresponding sequences can be obtained from the other by the interchange of a \(0\) and \(1\). If \(G\) is a graph of order \(m\) that can be realized as the distance graph of \(0-1\) sequences, then we prove that the \(0-1\) sequences require length at most \(2m-2\). We present a list of minimal forbidden induced subgraphs of distance graphs of \(0-1\) sequences.

A distance graph \(D(G)\) has vertices from some set \(G\) of graphs or \(k\)-stratified graphs. Two vertices are adjacent if one of the corresponding graphs can be obtained from the other by a single edge rotation. We prove that \(K_n\) minus an edge is a distance graph of a set of graphs. We fully characterize which radius one graphs are distance graphs of \(0-1\) sequences and which are distance graphs of graphs with distinctly labelled vertices.

The vertices of the queen’s graph \(Q_n\) are the squares of an \(n \times n\) chessboard and two squares are adjacent if a queen placed on one covers the other. Informally, a set \(I\) of queens on the board is irredundant if each queen in \(I\) covers a square (perhaps its own) which is not covered by any other queen in \(I\). It is shown that the cardinality of any irredundant set of vertices of \(Q_n\) is at most \(\left\lfloor {6n+6-8}\sqrt{n+3} \right\rfloor\) for \(n \geq 6\). We also show that the bound is not exact since \(\mathrm{IR}(Q_8) \leq 23\).

The star graph \(S_n\) is a graph with \(S_n\), the set of all permutations over \(\{1, \ldots, n\}\) as its vertex set; two vertices \(\pi_1\) and \(\pi_2\) are connected if \(\pi_1\) can be obtained from \(\pi_2\) by swapping the first element of \(\pi_2\) with one of the other \(n-1\) elements. In this paper we establish the genus of the star graph. We show that the genus, \(g_n\) of \(S_n\) is exactly equal to \(n!(n-4)/6+1\) by establishing a lower bound and inductively giving a drawing on a surface of appropriate genus.

In this note, a conjecture of P. Johnson Jr. on the Hall condition number is disproved.

Each vertex of a graph \(G = (V, E)\) is said to dominate every vertex in its closed neighborhood. A set \(S \subseteq V\) is a double dominating set for \(G\) if each vertex in \(V\) is dominated by at least two vertices in \(S\). The smallest cardinality of a double dominating set is called the double domination number \(dd(G)\). We initiate the study of double domination in graphs and present bounds and some exact values for \(dd(G)\). Also, relationships between \(dd(G)\) and other domination parameters are explored. Then we extend many results of double domination to multiple domination.

We investigate the following problem: given a set \(S \subset \mathbb{R}^2\) in general position and a positive integer \(k\), find a family of matchings \(\{M_1, M_2, \ldots, M_k\}\) determined by \(S\) such that if \(i \neq j\) then each segment in \(M_i\) crosses each segment in \(M_j\). We give improved linear lower bounds on the size of the matchings in such a family.

In this paper, we improve the upper bounds for the genus of the group \(\mathcal{A} = {Z}_{m_1} \times {Z}_{m_2} \times {Z}_{m_3}\) (in canonical form) with at least one even \(m_i\), \(i = 1, 2, 3\). As a special case, our results reproduce the known results in the cases \(m_3 = 3\) or both \(m_2\) and \(m_3\) are equal to \(3\).