It has been conjectured that the smallest cardinality \(\theta(G)\) of a perfect neighbourhood set of a graph is bounded above by ir\((G)\), the smallest order of a maximal irredundant set.
We prove results concerning the construction of perfect neighbourhood sets from irredundant sets which could help to resolve the conjecture and which establish that \(\theta(G) \leq \text{ir}(G)\) in certain cases.
In particular, the inequality is proved for claw-free graphs and for any graph which has an ir-set \(S\) whose induced subgraph has at most six non-isolated vertices.

We introduce and study two new parameters, namely the upper harmonious chromatic number, \(H(G)\), and the upper line-distinguishing chromatic number, \(H'(G)\), of a graph \(G\).
\(H(G)\) is defined as the maximum cardinality of a minimal harmonious coloring of a graph \(G\), while \(H'(G)\) is defined as the maximum cardinality of a minimal line-distinguishing coloring of a graph \(G\).
We show that the decision problems corresponding to the computation of the upper line-distinguishing and upper harmonious chromatic numbers are NP-complete for general graphs \(G\).
We then determine \(H'(P_n)\) and \(H(P_n)\).
Lastly, we show that \(H\) and \(H’\) are incomparable, even for trees.

For a graph \(G\), assign an integer value weight to each edge. For a vertex \(v\), the label of v is the sum of weights of the edges incident with it. Further, the weighting is irregular if all the vertex labels are distinct. It is well known that if \(G\) has at most one isolated vertex and no isolated edges, then there exist irregular assignments, in fact, using positive edge weights.

In this paper, we consider the following special weighting:
\vspace{0.5cm}

– If \(G\) has order \( 2 k + 1\), then a consecutive labeling is an assignment where the vertex labels are precisely \(-k, -k+1, \ldots, -1, 0, 1, 2, \ldots, k-1, k\).

– If \(G\) has order \( 2k\), then a consecutive labeling is an assignment where the vertex labels are precisely \( -k+1, \ldots, -1, 0, 0, 1, 2, \ldots, k-1\).
\vspace{0.5cm}
Here we show that every graph which has an irregular assignment also has a consecutive labeling. This concept is extended by considering all consecutive labelings and looking for one that has the smallest maximum, in absolute value, edge weight. This weight is referred to as the consecutive strength. Results parallel to the concept of irregularity strength are presented.

A modification of the Schreier-Sims algorithm is described which builds a permutation group utilising the transitivity of the stabiliser subgroups. Alternating and symmetric groups are recognised by their transitivity, resulting in a greatly improved time to build symmetric and alternating groups.
The algorithm has applications to graph isomorphism and other combinatorial isomorphism algorithms, as well as permutation group algorithms.

Suppose \(G = (V, E)\) is a graph in which every vertex \(v\) has a non-negative real number \(\omega(v)\) as its weight. The \(\omega\)-distance sum of \(v\) is \(D_{G,\omega}(v) = \sum_{u \in V} d(v, u)\omega(u).\) The \(\omega\)-median \(M_\omega(G)\) of \(G\) is the set of all vertices \(v\) with minimum \(\omega\)-distance sum \(D_{G,\omega}(v)\). This paper gives linear-time algorithms for computing the \(\omega\)-medians of interval graphs and block graphs.

Let \(p\) denote the number of vertices in a graph and let \(q\) denote the number of edges. Two cycles in a graph are disjoint if they have no common vertices. Pósa proved that any graph with \(q \geq 3p – 5\) contains two disjoint cycles. This result does not apply to planar graphs, since every planar graph has \(q \leq 3p – 6\).
In this paper, I show that any planar graph with \(q \geq 2p\) contains two disjoint cycles. I also show that this bound is best possible and that there is no minimum number of edges in a planar graph which will ensure the graph contains \(3\) disjoint cycles. Furthermore, a sufficient condition for any triangle-free graph (and therefore any bipartite graph) to contain \(k\) disjoint cycles is given.

The domination graph of a digraph is the graph on the same vertices with an edge between two vertices if every other vertex loses to at least one of the two. This note describes which connected graphs are domination graphs of tournaments.

Sharp invariant relationships involving various types of domination numbers are found
between a graph and its line graph.

A well-known problem in domination theory is the long-standing conjecture of V.G. Vizing from 1963 (see [7]) that the domination number of the Cartesian product of two graphs is at least as large as the product of the domination numbers of the individual graphs.
Although limited progress has been made, this problem essentially remains open. The usefulness of a maximum 2-packing in one of the graphs in establishing a lower bound has been recognized for some time.
In this paper, we shall extend this approach so as to take advantage of 2-packings whose membership can be altered in a certain way. This results in an improved lower bound for graphs which have 2-packings of this type.

A graph \(G\) is claw-free if it does not contain any complete bipartite graph \(K_{1,3}\) as an induced subgraph, and closed claw-free if it is the line-graph of a triangle-free graph. The inflation \(H_1\) of a graph \(H\) is obtained from \(\mathop{H}\limits^{i}\) by replacing each vertex \(x\) of degree \(d(x)\) by a clique \(X \simeq K_{d(x)}\).
Every inflated graph \(G = H_1\) is closed claw-free.
The minimum cardinalities \(\gamma(G)\), \(\text{ir}(G)\), and \(\text{rai}(G)\) of respectively a dominating set, a maximal irredundant set, and an \(R\)-annihilated irredundant set of any graph \(G\) satisfy
\(\text{rai}(G) \leq \text{ir}(G) \leq \gamma(G).\)
The motivation of this paper is that for inflated graphs, it is known that the difference \(\gamma(G) – \text{ir}(G)\) can be arbitrarily large, but not how large the ratio \(\gamma(G)/\text{ir}(G)\) can be. We show that \(\gamma(G) \leq 3\text{rai}(G)/2\) for every claw-free graph \(G\) and study the sharpness of the bounds
\(1 \leq {\gamma(G)}/{\text{ir}(G)} \leq {\gamma(G)}/{\text{rai}(G)} \leq {3}/{2}\)
in the four classes of claw-free graphs, closed claw-free graphs, inflated graphs, and line graphs of bipartite graphs.

Let \(\tau(G)\) denote the number of vertices in a longest path of the graph \(G = (V, E)\). A subset \(K\) of \(V\) is called a \(P_n\)-\emph{kernel} of \(G\) if \(\tau(G[K]) \leq n – 1\) and every vertex \(v \in V(G – K)\) is adjacent to an end-vertex of a path of order \(n – 1\) in \(G[K]\).
A partition \(\{A, B\}\) of \(V\) is called an \((a, b)\)-partition if \(\tau(G[A]) \leq a\) and \(\tau(G[B]) \leq b\).
We show that any graph with girth greater than \(n – 3\) has a \(P_n\)-kernel and that every graph has a \(P_\gamma\)-kernel. As corollaries of these results, we show that if \(\tau(G) = a + b\) and \(G\) has girth greater than \(a – 2\) or \(a \leq 6\), then \(G\) has an \((a, b)\)-partition.

In this paper, we establish that for arbitrary positive integers k and m, where \(k > 1\), there exists a tournament which has exactly m minimum dominating sets of order k. A construction of such tournaments will be given.

A connected graph \(G\) is \((\gamma, k)\)-insensitive if the domination number \(\gamma(G)\) is unchanged when an arbitrary set of \(k\) edges is removed. The problem of finding the least number of edges in any such graph has been solved for \(k = 1\) and for \(k = \gamma(G) = 2\). Asymptotic results as \(n\) approaches infinity are known for \(k \geq 2\) and \(k+1 \leq \gamma(G) \leq 2k\). Note that for \(k = 2\), this bound holds only for graphs \(G$ with \(\gamma(G) \in \{3,4\}\). In this paper, we present an asymptotic bound for the minimum number of edges in an extremal \((\gamma, k)\)-insensitive graph \(G\), where \(k = 2\) and \(n \geq 3\gamma(G)^2 – 2\gamma(G) + 3\) that holds for \(\gamma(G) \geq 3\). For small \(n\), we present tighter bounds (in some cases exact values) for this minimum number of edges.

A queen on a hexagonal board with hexagonal cells is defined as a piece that moves along three lines, namely along the cells in the same row, up diagonal, or down diagonal. A queen dominates a cell if the cell is in the same line as the queen.
We show that hexagonal boards with \(n \geq 1\) rows and diagonals, where \(n \equiv 3 \pmod{4}\), have only two types of minimum dominating sets. We also determine the irredundance numbers of the boards with \(5\) and \(7\) rows.

A well-spread sequence is an increasing sequence of distinct positive integers whose pairwise sums are distinct. Some properties of these sequences are discussed.

In this note, we consider finite, undirected, and simple graphs. A subset \(D\) of the vertex set of a graph \(G\) is a dominating set if each vertex of \(G\) is either in \(D\) or adjacent to some vertex of \(D\). A dominating set of minimum cardinality is called a minimum dominating set
A vertex \(v\) of a graph \(G\) is called a cut-vertex of G if \(G – v\) has more components than \(G\). A block of a graph is a maximal connected subgraph having no cut-vertex.
A block-cactus graph is a graph whose blocks are either complete graphs or cycles, and we speak of a cactus if the complete graphs consist of only one edge.
In our main theorem, we shall show that the minimum dominating set problem of an arbitrary graph can be reduced to its blocks. This theorem provides a linear-time algorithm for determining a minimum dominating set in a block-cactus graph, and thus, it can be seen as a supplement to a linear-time algorithm for finding a minimum dominating set in a cactus, presented by S.T. Hedetniemi, R.C. Laskar, and J. Pfaff in 1986.

For a graph facility or multi-facility location problem, each vertex is typically considered to be the location for one customer or one facility. Typically, the number of facilities is predetermined, and one must optimally locate these facilities so as to minimize some function of the distances between customers and facilities (and, perhaps, of the distances among the facilities). For example, p facility locations (such as, for hospitals or fire stations) might be chosen so as to minimize the maximum or the average distance from a customer to the nearest facility. The problem investigated in this paper considers all of the facilities to be distinct, and we seek to minimize the average customer-to-facility distance, primarily for grid graphs.

Let \(G = (V, E)\) be a graph.A set \(S \subseteq V\) is a dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\).The domination number of \(G\), denoted by \(\gamma(G)\), is the minimum cardinality of a dominating set of \(G\).Sanchis [8] showed that a connected graph \(G\) of size \(q\) and minimum degree at least \(2\) has domination number at most \((q+2)/3\).
In this paper, connected graphs \(G\) of size \(q\) with minimum degree at least \(2\) satisfying \(\gamma(G) > \frac{q}{3}\) are characterized.

For two vertices \(u\) and \(v\) in a strong oriented graph \(D\) of order \(n \geq 3\), the strong distance \(\text{sd}(u,v)\) between \(u\) and \(v\) is the minimum size of a strong subdigraph of \(D\) containing \(u\) and \(v\). For a vertex \(v\) of \(D\), the strong eccentricity \(\text{se}(v)\) is the strong distance between \(v\) and a vertex farthest from \(v\). The minimum strong eccentricity among the vertices of \(D\) is the strong radius \(\text{srad}(D)\), and the maximum strong eccentricity is its strong diameter \(\text{sdiam}(D)\). It is shown that every pair \(r,d\) of integers with \(3 \leq r \leq d \leq 2r\) is realizable as the strong radius and strong diameter of some strong oriented graph.
Moreover, for every strong oriented graph \(D\) of order \(n \geq 3\), it is shown that
\[
\text{sdiam}(D) \leq \left\lfloor \frac{5(n-1)}{3} \right\rfloor.
\]
Furthermore, for every integer \(n \geq 3\), there exists a strong oriented graph \(D\) of order \(n\) such that
\[
\text{sdiam}(D) = \left\lfloor \frac{5(n-1)}{3} \right\rfloor.
\]

For each vertex \(s\) of the subset \(S\) of vertices of a graph \(G\), we define Boolean variables \(p\), \(q\), \(r\) which measure the existence of three kinds of \(S\)-private neighbors (\(S\)-pns) of \(s\). A \(3\)-variable Boolean function \(f = f(p, q, r)\) may be considered as a compound existence property of \(S\)-pns. The set \(S\) is called an \(f\)-set of \(G\) if \(f = 1\) for all \(s \in S\), and the class of all \(f\)-sets of \(G\) is denoted by \(\Omega_f\). Special cases of \(\Omega_f\) include the
independent sets, irredundant sets, open irredundant sets, and CO-irredundant sets of \(G\).
There are \(62\) non-trivial families \(\Omega_f\) which include the \(7\) families of a framework proposed earlier by Fellows, Fricke, Hedetniemi, and Jacobs. The functions \(f\) for which \(\Omega_f\) is hereditary for any graph \(G\) are determined. Additionally, the existence and properties of \(f\)-Ramsey numbers (analogues of the elusive classical Ramsey numbers) are investigated, and future directions for the theory of the classes \(\Omega_f\) are considered.