Let \(\gamma(G)\) be the domination number of a graph \(G\). A class \(\mathcal{P}\) of graphs is called \(\gamma\)-complete if the problem of determining \(\gamma(G)\), \(G \in \mathcal{P}\), is NP-complete. A class \(\mathcal{P}\) of graphs is called \(\gamma\)-polynomial if there is a polynomial-time algorithm for calculating \(\gamma(G)\) for all graphs \(G \in \mathcal{P}\).

We denote \(\Gamma = \{P_k\cap nK_1 : k \leq 4 \text{ and } n \geq 0\}\). Korobitsin \([4]\) proved that if \(\mathcal{P}\) is a hereditary class defined by a unique forbidden induced subgraph \(H\), then

1. when \(H \in \Gamma\), \(\mathcal{P}\) is a \(\gamma\)-polynomial class,
2. when \(H \notin \Gamma\), \(\mathcal{P}\) is a \(\gamma\)-complete class.

We extend a positive result (i) in the following way. The class \(\Gamma\) is hereditary, and it is characterized by the set

\[Z(\Gamma) = \{2K_2, K_{1,3},C_3,C_4,C_5\}\]

of minimal forbidden induced subgraphs.

For each \(Z \subseteq Z(\Gamma)\) we consider a hereditary class \({FIS}(Z)\) defined by the set \(Z\) of minimal forbidden induced subgraphs. We prove that \(\mathcal{FIS}(Z)\) is \(\gamma\)-complete in 16 cases, and it is \(\gamma\)-polynomial in the other 16 cases. We also prove that \(2K_2\)-free graphs with bounded clique number constitute a \(\gamma\)-polynomial class.

Let \(G = (V, E)\) be a connected graph and \(S \subseteq E\). \(S\) is said to be an \(r\)-restricted edge cut if \(G – S\) is disconnected and each component in \(G – S\) contains at least \(r\) vertices. Define \(\lambda^{(r)}(G)\) to be the minimum size of all \(r\)-restricted edge cuts and \(\xi_r(G) = \min\{w(U): U \subseteq V, |U| = r\) and the subgraph of \(G\) induced by \(U\) is connected, where \(w(U)\) denotes the number of edges with one end in \(U\) and the other end in \(V\setminus U\). A graph \(G\) with \(\lambda^{(r)} = \xi_r(G)\) (\(r = 1,2,3\)) is called an \(\lambda^{(3)}\)-optimal graph. In this paper, we show that the only edge-transitive graphs which are not \(\lambda^{(3)}\)-optimal are the star graphs \(K_{1, n-1}\), the cycles \(C_n\), and the cube \(Q_3\). Based on this, we determine the expressions of \(N_i(G)\) (\(i = 0,1,\ldots,\xi_3(G) – 1\)) for edge transitive graph \(G\), where \(N_i(G)\) denotes the number of edge cuts of size \(i\) in \(G\).

A vertex-deleted subgraph (subdigraph) of a graph (digraph) \(G\) is called a card of \(G\). A card of \(G\) with which the degree (degree triple) of the deleted vertex is also given is called a degree associated card or dacard of \(G\). To investigate the failure of digraph reconstruction conjecture and its effect on Ulam’s conjecture, we study the parameter \(\textbf{degree associated reconstruction number}\) \(drm(G)\) of a graph (digraph) \(G\) defined as the minimum number of dacards required in order to uniquely identify \(G\). We find \(drm\) for some classes of graphs and prove that for \(t\geq 2\), \(drm(tG)\leq 1+drm(G)\) when \(G\) is connected nonregular and \(drm(tG)\leq m+2-r\) when \(G\) is connected \(r\)-regular of order \(m>2\) and these bounds are tight. \(drm \leq 3\) for other disconnected graphs. Corresponding results for digraphs are also proved.

Two parameters for measuring irregularity in graphs are the degree variance and the discrepancy. We establish best possible upper bounds for the discrepancy in terms of the order and average degree of the graph, and describe some extremal graphs, thereby providing analogues of results of [1], [4] and [5] for the degree variance.

It is calculated the number of symmetric \(r\)-colorings of vertices of a regular \(n\)-gon and the number of equivalence classes of symmetric \(r\)-colorings. A coloring is symmetric if it is invariant with respect to some mirror symmetry with an axis crossing the center of polygon and one of its vertices. Colorings are equivalent if we can get one from another by rotating about the polygon center.

A graph \(G\) is said to be excellent if, given any vertex \(x\) of \(G\), there is a \(\gamma\)-set of \(G\) containing \(x\). It is known that any non-excellent graph can be imbedded in an excellent graph. For example, for every graph \(G\), its corona \(G \circ K\) is excellent, but the difference \(\gamma(G \circ K) – \gamma(G)\) may be high. In this paper, we give a construction to imbed a non-excellent graph \(G\) in an excellent graph \(H\) such that \(\gamma(H) \leq \gamma(G) + 2\). We also show that, given a non-excellent graph \(G\), there is a subdivision of \(G\) which is excellent. The excellent subdivision number of a graph \(G\), \(ESdn{G}\), is the minimum number of edges of \(G\) to be subdivided to get an excellent subdivision graph \(H\). We obtain upper bounds for \(ESdn{G}\). If any one of these upper bounds for \(ESdn{G}\) is attained, then the set of all vertices of \(G\) which are not in any \(\gamma\)-set of \(G\) is an independent set.

In this paper, using the \(q\)-exponential operator technique to Bailey’s \(\mathop{_2\psi_2}\) transformation, we obtain some interesting \(\mathop{_3\psi_3}\)
transformation formulae and summation theorems.

MacGillivray and Seyffarth (J. Graph Theory \(22 (1996),213-229)\) proved that planar graphs of diameter three have domination number at most ten. Recently it was shown (J. Graph Theory \(40 (2002), 1-25)\) that a planar graph of diameter three and of radius two has domination number at most six while every sufficiently large planer graph of diameter three has domination number at most seven. In this paper we improve on these results. We prove that every planar graph of diameter three and of radius two has total domination number (and therefore domination number) at most five. We show then that every sufficiently large planar graph of diameter three has domination number at most six and this result is sharp, while a planar graph of diameter three has domination number at most nine.

A hypergraph is a generalization of an ordinary graph, in which an edge is not limited to contain exactly two vertices, instead, it can contain an arbitrary number of vertices. A number of desirable properties of database schemes have been shown to be equivalent to hypergraphs. In addition, hypergraph models are very important for cellular mobile communication systems. By applying Pólya’s Enumeration Theorem (PET) twice, the counting series is derived for unlabeled linear acyclic hypergraphs in this paper.

In a given graph \(G\), a set \(S\) of vertices with an assignment of colors is a defining set of the vertex coloring of \(G\), if there exists a unique extension of the colors of \(S\) to a \(\chi(G)\)-coloring of the vertices of \(G\). A defining set with minimum cardinality is called a smallest defining set (of vertex coloring) and its cardinality, the defining number, is denoted by \(d(G, \chi)\). Let \(d(n,r, \chi = k)\) be the smallest defining number of all \(r\)-regular \(k\)-chromatic graphs with \(n\) vertices. Mahmoodian and Mendelsohn (1999) proved that for each \(n\geq m\) and each \(r \geq 4\), \(d(n,r, \chi = 3) = 2\). They raised the following question: Is it true that for every \(k\), there exist \(n_0(k)\) and \(r_0(k)\), such that for all \(n \geq n_0(k)\) and \(r \geq r_0(k)\) we have \(d(n,r, \chi = k) = k-1\)? We show that the answer to this question is positive, and we prove that for a given \(k\) and for all \(n \geq 3k\), if \(r \geq 2(k – 1)\) then \(d(n,r, \chi = k) = k-1\).