Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). A (defensive) alliance in \(G\) is a subset \(S\) of \(V(G)\) such that for every vertex \(v \in S\), \(|N(v) \cap S| \geq |N(v) \cap (V(G) – S)|\). The alliance partition number of a graph \(G\), \(\psi_a(G)\), is defined to be the maximum number of sets in a partition of \(V(G)\) such that each set is a (defensive) alliance. In this paper, we give both general bounds and exact results for the alliance partition number of graphs, and in particular for regular graphs and trees.

In this paper, we present a unified and simple approach to extremal acyclic graphs without perfect matching for the energy, the Merrifield-Simmons index and Hosoya index.

The notion of equitable coloring was introduced by Meyer in \(1973\). In this paper, we obtain interesting results regarding the equitable chromatic number \(\chi=\) for the sun let graphs \(S_n\), line graph of sun let graphs \(L(S_n)\), middle graph of sun let graphs \(M(S_n)\), and total graph of sun let graphs \(T(S_n)\).

Kühn and Osthus \([2]\) proved that for every positive integer \(\ell\), there exists an integer \(k(\ell) \leq 2^{11}.3\ell^2\), such that the vertex set of every graph \(G\) with \(\delta(G) \geq k(\ell)\) can be partitioned into subsets \(S\) and \(T\) with the properties that \(\delta(G[S]) \geq \ell \leq \delta(G[T])\) and every vertex of \(S\) has at least \(\ell\) neighbors in \(T\). In this note, we improve the upper bound to \(k(\ell) \leq 2^4 – 17\ell^2\).

In this paper, we discuss how the addition of a new edge changes the irregularity strength in \(K(3,n)\), \(tK_3\), and \(tP_4\).

For a graph \(G\), the Merrifield-Simmons index \(i(G)\) and the Hosoya index \(z(G)\) are defined as the total number of independent sets and the total number of matchings of the graph \(G\), respectively. In this paper, we characterize the graphs with the maximal Merrifield-Simmons index and the minimal Hosoya index, respectively, among the bicyclic graphs on \(n\) vertices with a given girth \(g\).

In this paper, we study the existence of \(\alpha\)-labelings for trees by means of particular \((0, 1)\)-matrices called \(a\)-labeling matrices. It is shown that each comet \(S_{k, q}\) admits no \(a\)-labelings whenever \(k > 4(q – 1)\) and \(q \geq 2\). We also give the sufficient conditions for the nonexistence of \(a\)-labelings for trees of diameter at most six. This extends a result of Rosa’s. As a consequence, we prove that \(S_{k, 3}\) has an \(a\)-labeling if and only if \(k \leq 4\).

Given a graph \(G\), an independent set \(I(G)\) is a subset of the vertices of \(G\) such that no two vertices in \(I(G)\) are adjacent. The independence number \(\alpha(G)\) is the order of a largest set of independent vertices. In this paper, we study the independence number for the Generalized Petersen graphs, finding both sharp bounds and exact results for subclasses of the Generalized Petersen graphs.

In this note, we show that the variety of Boolean \(SQS\)-skeins can be defined by a single axiom and, in the process, we find all of the shortest single axioms for said variety. Our investigations were aided by the automated theorem-prover Prover9 and the finite model-finder Mace4.

Let \(G(V,E)\) be a graph. A subset \(S\) of \(V\) is called a dominating set of \(G\) if every vertex in \(V-S\) is adjacent to at least one vertex in \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality taken over all dominating sets in \(G\). A dominating set \(S\) of \(G\) is called a complementary perfect dominating set (cpd-set) if the induced subgraph \(\langle V-S \rangle\) has a perfect matching. The complementary perfect domination number, \(\gamma_{cp}(G)\), of \(G\) is the minimum cardinality taken over all cpd-sets in \(G\).

An induced complementary perfect dominating set of a graph (icpd-set) is a dominating set of \(G\) such that the induced subgraph \(\langle V-S \rangle\) has only independent edges. That is, \(\langle V-S \rangle = mK_2\), \(m \geq 1\). The minimum cardinality taken over all such icpd-sets of \(G\) is called the induced complementary perfect domination number of \(G\), and is denoted by \(\gamma_{icp}(G)\).

A subset \(S\) of \(V\) is said to be a complementary connected dominating set (ccd-set) if \(S\) is a dominating set and \(\langle V-S \rangle\) is connected. The complementary connected domination number of a graph is denoted by \(\gamma_{cc}(G)\) and is defined as the minimum number of vertices which form a ccd-set.

It has been proved that \(\gamma_{cp}(G) = n = \gamma_{icp}(G)\) and \(\gamma_{cc}(G) = n-1\) only if \(G\) is a star. And if \(G\) is not a star, then \(\gamma_{cp}, \gamma_{icp}, \gamma_{cc} \leq n-2\). In this paper, we characterize the graphs with \(\gamma_{cc} \leq n-2\), and trees with \(\gamma_{cp} = n-2\) and \(\gamma_{icp} = n-2\).