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

In this paper subsets of a three-dimensional locally projective planar space which meet every plane either in \(2\) or in \(h, h > 2\), points are studied and classified.

Let \(G_1, G_2\) be simple graphs with \(n_1, n_2\) vertices and \(m_1, m_2\) edges respectively. The Corona graph \(G_1 \circ G_2\) of \(G_1\) with \(G_2\) is obtained by taking one copy of \(G_1\), \(v_1\) copies of \(G_2\) and then joining each vertex of \(G_1\) to all the vertices of a copy of \(G_2\).

For a graph \(G\), by the index of cordiality \(i(G)\) we mean \(\min{|e_f(0)-e_f(1)|}\), where the minimum is taken over all the binary labelings of \(G\) with \(|v_f(0)-v_f(1)|\leq 1\). In this paper, we investigate the cordiality of \(G_1 \circ \overline{K_t}, K_n \circ \overline{K_t}\) and \(G \circ C_t\), where \(G\) is a graph with the index of cordiality \(k\).

In this paper, we give a necessary condition for an odd degree graph to be Skolem-graceful and we prove that if \(G\) is a \((p, q)\) pseudograceful graph such that \(p=q+tl\), then \(G\cup S_m\) is Skolem-graceful for all \(m\geq 1\). Finally, we give some variations on the definition of cordial graphs.

The posets of dimension \(2\) are those posets whose minimal realizations have two elements, that is, which may be obtained as the intersection of two of their linear extensions. Gallai’s decomposition of a poset allows for a simple formula to count the number of the distinct minimal realizations of the posets of dimension \(2\). As an easy consequence, the characterization of M. El-Zahar and of N.W. Sauer of the posets of dimension \(2\), with an unique minimal realization, is obtained.

In this paper we give a new method for constructing modular \(n\)-queens solutions which, in particular, yields nonlinear solutions for all composite \(n\) such that \(\gcd(n,6) = 1\) and all prime \(n \geq 19\).

Path problems in graphs can generally be formulated and solved by using an algebraic structure whose instances are called path algebras. Each type of path problem is characterized by a different instance of the structure. This paper proposes a method for combining already known path algebras into new ones. The obtained composite algebras can be applied to solve relatively complex path problems, such as explicit identification of optimal paths or multi-criteria optimization. The paper presents proofs showing that the proposed construction is correct. Also, prospective applications of composite algebras are illustrated by examples. Finally, the paper explores possibilities of making the construction more general.

Automorphisms of Steiner \(2\)-designs \(S(2,4,37)\) are studied and used to find many new examples. Some of the constructed designs have \(S(2,3,9)\) subdesigns, closing the last gap in the embedding spectrum of \(S(2,3,9)\) designs into \(S(2,4,v)\) designs.

We give a construction for a new family of Group Divisible Designs \((6s + 2, 3, 4; 2, 1)\) using Mutually Orthogonal Latin Squares for all positive integers \(s\). Consequently, we have proved that the necessary conditions are sufficient for the existence of GDD’s of block size four with three groups, \(\lambda_1 = 2\) and \(\lambda_2 = 1\).

For a balanced incomplete block (BIB) design, the following problem is considered: Find \(s\) different incidence matrices of the BIB design such that (i) for \(1 \leq t \leq s-1\), sums of any \(t\) different incidence matrices yield BIB designs and (ii) the sum of all \(s\) different incidence matrices becomes a matrix all of whose elements are one. In this paper, we show general results and present four series of such BIB designs with examples of three other BIB designs.

The extremal matrix problem of symmetric primitive matrices has been completely solved in [Sci. Sinica Ser.A 9(1986) 931-939] and [Linear Algebra Appl.133(1990) 121-131]. In this paper, we determine the maximum exponent in the class of central symmetric primitive matrices, and give a complete characterization of those central symmetric primitive matrices whose exponents actually attain the maximum exponent.

Using a similar framework to \([7]\), we construct a family of relative difference sets in \(P \times ({Z}_{p^2r}^2t)\), where \(P\) is the forbidden subgroup. We only require that \(P\) be an abelian group of order \(p^t\). The construction makes use of character theory and the structure of the Galois ring \(GR(p^{2r}, t)\), and in particular the Teichmüller set for the Galois ring.

Let \(G\) be a graph, and let \(g\) and \(f\) be two integer-valued functions defined on \(V(G)\) such that \(g(x) \leq f(x)\) for all \(x \in V(G)\). A graph \(G\) is called a \((g, f, n)\)-critical graph if \(G-N\) has a \((g, f)\)-factor for each \(N \subseteq V(G)\) with \(|N| = n\). In this paper, a necessary and sufficient condition for a graph to be \((g, f, n)\)-critical is given. Furthermore, the properties of \((g, f, n)\)-critical graphs are studied.

The object of this paper is to give solutions to some of the problems suggested by A.K. Agarwal[\(n\)-color Analogues of Gaussian Polynomials, Ars Combinatoria \(61 (2001), 97-117\)].

For \(n \geq 1\), let \(p(n)\) denote the smallest natural number \(r\) for which the following is true: For \(K\) any finite family of simply connected orthogonal polygons in the plane and points \(x\) and \(y\) in \(\cap\{K : K \in \mathcal{K}\}\), if every \(r\) (not necessarily distinct) members of \(K\) contain a common staircase \(n\)-path from \(x\) to \(y\), then \(\cap\{K : K \in \mathcal{K}\}\) contains such a staircase path. It is proved that \(p(1) = 1, p(2) = 2, p(3) = 4, p(4) = 6\), and \(p(n) \leq 4 + 2p(n – 2)\) for \(n \geq 5\).

The numbers \(p(n)\) are used to establish the following result. For \(\mathcal{K}\) any finite family of simply connected orthogonal polygons in the plane, if every \(3p(n + 1)\) (not necessarily distinct) members of \(\mathcal{K}\) have an intersection which is starshaped via staircase \(n\)-paths, then \(\cap\{K : K \in \mathcal{K}\}\) is starshaped via staircase \((n+1)\)-paths. If \(n = 1\), a stronger result holds.

A \((p,q)\) graph \(G\) is called edge-magic if there exists a bijective function \(f: V(G) \cup E(G) \to \{1,2,\ldots,p+q\}\) such that \(f(u) + f(v) + f(uv) = k\) is a constant for any edge \(uv \in E(G)\). Moreover, \(G\) is said to be super edge-magic if \(f(V(G)) = \{1,2,\ldots, p\}\). The question studied in this paper is for which graphs it is possible to add a finite number of isolated vertices so that the resulting graph is super edge-magic. If it is possible for a given graph \(G\), then we say that the minimum such number of isolated vertices is the super edge-magic deficiency, \(\mu_s(G)\) of \(G\); otherwise we define it to be \(+\infty\).

In this article, we discuss the Helly property and the strong Helly property in hypergraphs. We give a characterization of neighborhood hypergraphs having the Helly and the strong Helly property. These properties are studied in both Cartesian and strong products of hypergraphs.

There are several well-known and important Hamiltonian results for claw-free graphs, but only a few are concerned with quasi-claw-free graphs. In this note, we provide a new sufficient condition for quasi-claw-free Hamiltonian graphs.

A \(d\)-antimagic labeling of a plane graph \(G = (V, E, F)\) is a one-to-one mapping taking the vertices, edges, and faces onto the integers \(1, 2, \ldots, |V(G)| + |E(G)| + |F(G)|\) so that the \(s\)-sided face weights form an arithmetic progression of difference \(d\). This paper describes \(d\)-antimagie labelings for Möbius grids.