Let \(G = (V(G), E(G))\) be a graph. A set \(S \subseteq V(G)\) is a dominating set if every vertex of \(V(G) – S\) is adjacent to some vertices in \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality of a dominating set of \(G\). In this paper, we study the domination number of generalized Petersen graphs \(P(n,3)\) and prove that \(\gamma(P(n,3)) = n – 2\left\lfloor \frac{n}{4} \right\rfloor (n\neq 11)\).

The maximality of the Suzuki group \(\text{Sz}(K,a)\), \(K\) any commutative field of characteristic \(2\) admitting an automorphism \(\sigma\) such that \(x^{\sigma^2} = x^2\), in the symplectic group \(\text{PSp}_4(K)\), is proved.

Let \(k\) be a positive integer and \(G = (V, E)\) be a connected graph of order \(n\). A set \(D \subseteq V\) is called a \(k\)-dominating set of \(G\) if each \(x \in V(G) – D\) is within distance \(k\) from some vertex of \(D\). A connected \(k\)-dominating set is a \(k\)-dominating set that induces a connected subgraph of \(G\). The connected \(k\)-domination number of \(G\), denoted by \(\gamma_k^c(G)\), is the minimum cardinality of a connected \(k\)-dominating set. Let \(\delta\) and \(\Delta\) denote the minimum and the maximum degree of \(G\), respectively. This paper establishes that \(\gamma_k^c(G) \leq \max\{1, n – 2k – \Delta + 2\}\), and \(\gamma_k^c(G) \leq (1 + o_\delta(1))n \frac{ln[m(\delta+1)+2-t]}{m(\delta+1)+2-t}\), where \(m = \lceil \frac{k}{3} \rceil\), \(t = 3 \lceil \frac{k}{3} \rceil – k\), and \(o_\delta(1)\) denotes a function that tends to \(0\) as \(\delta \to \infty\). The later generalizes the result of Caro et al. in [Connected domination and spanning trees with many leaves. SIAM J. Discrete Math. 13 (2000), 202-211] for \(k = 1\).

A graph \(U\) is (induced)-universal for a class of graphs \({X}\) if every member of \({X}\) is contained in \(U\) as an induced subgraph. We study the problem of finding universal graphs with minimum number of vertices for various classes of bipartite graphs: exponential classes, bipartite chain graphs, bipartite permutation graphs, and general bipartite graphs. For exponential classes and general bipartite graphs we present a construction which is asymptotically optimal, while for the other classes our solutions are optimal in order.

The multicolor Ramsey number \(R_r(H)\) is defined to be the smallest integer \(n = n(r)\) with the property that any \(r\)-coloring of the edges of complete graph \(K_n\) must result in a monochromatic subgraph of \(K_n\) isomorphic to \(H\). In this paper, we study the case that \(H\) is a cycle of length \(2k\). If \(2k \geq r+1\) and \(r\) is a prime power, we show that \(R_r(C_{2k}) > {r^2+2k-r-1}\).

The bondage number \(b(D)\) of a digraph \(D\) is the cardinality of a smallest set of arcs whose removal from \(D\) results in a digraph with domination number greater than the domination number of \(D\). In this paper, we present some upper bounds on bondage number for oriented graphs including tournaments, and symmetric planar digraphs.

Let \(G\) be a connected graph. For a vertex \(v \in V(G)\) and an ordered \(k\)-partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) of \(V(G)\), the representation of \(v\) with respect to \(\Pi\) is the \(k\)-vector \(r(v|\Pi) = (d(v, S_1), d(v, S_2), \ldots, d(v, S_k))\). The \(k\)-partition \(\Pi\) is said to be resolving if the \(k\)-vectors \(r(v|\Pi), v \in V(G)\), are distinct. The minimum \(k\) for which there is a resolving \(k\)-partition of \(V(G)\) is called the partition dimension of \(G\), denoted by \(pd(G)\). A resolving \(k\)-partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) of \(V(G)\) is said to be connected if each subgraph \(\langle S_i \rangle\) induced by \(S_i\) (\(1 \leq i \leq k\)) is connected in \(G\). The minimum \(k\) for which there is a connected resolving \(k\)-partition of \(V(G)\) is called the connected partition dimension of \(G\), denoted by \(cpd(G)\). In this paper, the partition dimension as well as the connected partition dimension of the wheel \(W_n\) with \(n\) spokes are considered, by showing that \(\lceil (2n)^{1/3} \rceil \leq pd(W_n) \leq \lceil 2(n)^{1/2} \rceil +1\) and \(cpd(W_n) = \lceil (n+2)/3 \rceil\) for \(n \geq 4\).

Vertices \(x\) and \(y\) are called paired in tournament \(T\) if there exists a vertex \(z\) in the vertex set of \(T\) such that either \(x\) and \(y\) beat \(z\) or \(z\) beats \(x\) and \(y\). Vertices \(x\) and \(y\) are said to be distinguished in \(T\) if there exists a vertex \(z\) in \(T\) such that either \(x\) beats \(z\) and \(z\) beats \(y\), or \(y\) beats \(z\) and \(z\) beats \(x\). Two vertices are strictly paired (distinguished) in \(T\) if all vertices of \(T\) pair (distinguish) the two vertices in question. The \(p/d\)-graph of a tournament \(T\) is a graph which depicts strictly paired or strictly distinguished pairs of vertices in \(T\). \(P/d\)-graphs are useful in obtaining the characterization of such graphs as domination and domination-compliance graphs of tournaments. We shall see that \(p/d\)-graphs of tournaments have an interestingly limited structure as we characterize them in this paper. In so doing, we find a method of constructing a tournament with a given \(p/d\)-graph using adjacency matrices of tournaments.

Let \(G\) be a simple connected graph. The spectral radius \(\rho(G)\) of \(G\) is the largest eigenvalue of its adjacency matrix. In this paper, we obtain two lower bounds of \(\rho(G)\) by two different methods, one of which is better than another in some conditions.

In this note we compute the chromatic polynomial of the Jahangir graph \(J_{2p}\) and we prove that it is chromatically unique for \(p=3\).

In this paper, we compute the PI and Szeged indices of some important classes of benzenoid graphs, which some of them are related to nanostructures. Some open questions are also included.

The detour \(d(i, j)\) between vertices \(i\) and \(j\) of a graph is the number of edges of the longest path connecting these vertices. The matrix whose \((i, j)\)-entry is the detour between vertices \(i\) and \(j\) is called the detour matrix. The half sum \(D\) of detours between all pairs of vertices (in a connected graph) is the detour index, i.e.,

\[D = (\frac{1}{2}) \sum\limits_j\sum\limits_i d(i,j)\]

In this paper, we computed the detour index of \(TUC_4C_8(S)\) nanotube.

We construct several new group divisible designs with block size five and with \(2, 3\), or \(6\) groups.

A list \((2,1)\)-labeling \(\mathcal{L}\) of graph \(G\) is an assignment list \(L(v)\) to each vertex \(v\) of \(G\) such that \(G\) has a \((2,1)\)-labeling \(f\) satisfying \(f(v) \in L(v)\) for all \(v\) of graph \(G\). If \(|L(v)| = k + 1\) for all \(v\) of \(G\), we say that \(G\) has a \(k\)-list \((2,1)\)-labeling. The minimum \(k\) taken over all \(k\)-list \((2,1)\)-labelings of \(G\), denoted \(\lambda_l(G)\), is called the list label-number of \(G\). In this paper, we study the upper bound of \(\lambda(G)\) of some planar graphs. It is proved that \(\lambda_l(G) \leq \Delta(G) + 6\) if \(G\) is an outerplanar graph or \(A\)-graph; and \(\lambda_l(G) \leq \Delta(G) + 9\) if \(G\) is an \(HA\)-graph or Halin graph.

In this paper, we give a necessary and sufficient condition for a \(3\)-regular graph to be cordial.

This paper deals with the interconnections between finite weakly superincreasing distributions, the Fibonacci sequence, and Hessenberg matrices. A frequency distribution, to be called the Fibonacci distribution, is introduced that expresses the core of the connections among these three concepts. Using a Hessenberg representation of finite weakly superincreasing distributions, it is shown that, among all such \(n\)-string frequency distributions, the Fibonacci distribution achieves the maximum expected codeword length.

We present some applications of wall colouring to scheduling issues. In particular, we show that the chromatic number of walls has a very clear meaning when related to certain real-life situations.

Let \(G\) be a connected graph. For \(S \subseteq V(G)\), the geodetic closure \(I_G[S]\) of \(S\) is the set of all vertices on geodesics (shortest paths) between two vertices of \(S\). We select vertices of \(G\) sequentially as follows: Select a vertex \(v_1\) and let \(S_1 = \{v_1\}\). Select a vertex \(v_2 \neq v_1\) and let \(S_2 = \{v_1, v_2\}\). Then successively select vertex \(v_i \notin I_G[S_{i-1}]\) and let \(S_i = \{v_1, v_2, \ldots, v_i\}\). We define the closed geodetic number (resp. upper closed geodetic number) of \(G\), denoted \(cgn(G)\) (resp. \(ucgn(G)\)), to be the smallest (resp. largest) \(k\) whose selection of \(v_1, v_2, \ldots, v_k\) in the given manner yields \(I_G[S_k] = V(G)\). In this paper, we show that for every pair \(a, b\) of positive integers with \(2 \leq a \leq b\), there always exists a connected graph \(G\) such that \(cgn(G) = a\) and \(ucgn(G) = b\), and if \(a < b\), the minimum order of such graph \(G\) is \(b\). We characterize those connected graphs \(G\) with the property: If \(cgn(G) < k < ucgn(G) = 6\), then there is a selection of vertices \(v_1, v_2, \ldots, v_k\) as in the above manner such that \(I_G[S_k] = V(G)\). We also determine the closed and upper closed geodetic numbers of some special graphs and the joins of connected graphs.

Let \(G\) be a graph with \(n\) vertices and suppose that for each vertex \(v\) in \(G\), there exists a list of \(k\) colors, \(L(v)\), such that there is a unique proper coloring for \(G\) from this collection of lists, then \(G\) is called a uniquely \(k\)-list colorable graph. We say that a graph \(G\) has the property \(M(k)\) if and only if it is not uniquely \(k\)-list colorable. M. Ghebleh and E. S. Mahmoodian characterized uniquely \(3\)-list colorable complete multipartite graphs except for the graphs \(K_{1*4,5}\), \(K_{1*5,4}, K_{1*4,4}\), \(K_{2,3,4}\), and \(K_{2,2,r}\), \(4 \leq r \leq 8\). In this paper, we prove that the graphs \(K_{1*4,5}\), \(K_{1*5,4}\), \(K_{1*4,4}\), and \(K_{2,3,4}\) have the property \(M(3)\).

Let \(G\) be a simple graph and \(f: V(G) \mapsto \{1, 3, 5, \ldots\}\) an odd integer valued function defined on \(V(G)\). A spanning subgraph \(F\) of \(G\) is called a \((1, f)\)-odd factor if \(d_F(v) \in \{1, 3, \ldots, f(v)\}\) for all \(v \in V(G)\), where \(d_F(v)\) is the degree of \(v\) in \(F\). For an odd integer \(k\), if \(f(v) = k\) for all \(v\), then a \((1, f)\)-odd factor is called a \([1, k]\)-odd factor. In this paper, the structure and properties of a graph with a unique \((1, f)\)-odd factor is investigated, and the maximum number of edges in a graph of the given order which has a unique \([1, k]\)-odd factor is determined.

Erdős and Soifer \([3]\) and later Campbell and Staton \([1]\) considered a problem which was a favorite of Erdős \([2]\): Let \(S\) be a unit square. Inscribe \(n\) squares with no common interior point. Denote by \(\{e_1, e_2, \ldots, e_n\}\) the side lengths of these squares. Put \(f(n) = \max \sum\limits_{i=1}^n e_i\). And they discussed the bounds for \(f(n)\). In this paper, we consider its dual problem – covering a unit square with squares.

The well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph \(G\) in terms of the deficiency \(\max_{X \subseteq V(G)} \{ \omega_0(G – X) – |X| \}\) of \(G\), where \(\omega_0(H)\) denotes the number of odd components of \(H\). Let \(G’\) be the graph formed from \(G\) by subdividing (possibly repeatedly) a number of its edges. In this note we study the effect such subdivisions have on the difference between the size of a maximum matching in \(G\) and the size of a maximum matching in \(G’\).

In this paper, we give some necessary conditions for a prime graph. We also present some new families of prime graphs such as \(K_n \odot K_1\) is prime if and only if \(n \leq 7\), \(K_n \odot \overline{K_2}\) is prime if and only if \(n \leq 16\), and \(K_{m}\bigcup S_n\) is prime if and only if \(\pi(m+n-1) \geq m\). We also show that a prime graph of order greater than or equal to \(20\) has a nonprime complement.

Consider a lottery scheme consisting of randomly selecting a winning \(t\)-set from a universal \(m\)-set, while a player participates in the scheme by purchasing a playing set of any number of \(n\)-sets from the universal set prior to the draw, and is awarded a prize if \(k\) or more elements of the winning \(t\)-set occur in at least one of the player’s \(n\)-sets (\(1 \leq k \leq \{n,t\} \leq m\)). This is called a \(k\)-prize. The player may wish to construct a playing set, called a lottery set, which guarantees the player a \(k\)-prize, no matter which winning \(t\)-set is chosen from the universal set. The cardinality of a smallest lottery set is called the lottery number, denoted by \(L(m,n,t;k)\), and the number of such non-isomorphic sets is called the lottery characterisation number, denoted by \(\eta(m,n,t;k)\). In this paper, an exhaustive search technique is employed to characterise minimal lottery sets of cardinality not exceeding six, within the ranges \(2 \leq k \leq 4\), \(k \leq t \leq 11\), \(k \leq n \leq 12\), and \(\max\{n,t\} \leq m \leq 20\). In the process, \(32\) new lottery numbers are found, and bounds on a further \(31\) lottery numbers are improved. We also provide a theorem that characterises when a minimal lottery set has cardinality two or three. Values for the lottery characterisation number are also derived theoretically for minimal lottery sets of cardinality not exceeding three, as well as a number of growth and decomposition properties for larger lotteries.

Beck’s coloring is studied for meet-semilattices with \(0\). It is shown that for such semilattices, the chromatic number equals the clique number.

The main result of this paper is an upper bound on the number of independent sets in a tree in terms of the order and diameter of the tree. This new upper bound is a refinement of the bound given by Prodinger and Tichy [Fibonacci Q., \(20 (1982), no. 1, 16-21]\). Finally, we give a sufficient condition for the new upper bound to be better than the upper bound given by Brigham, Chandrasekharan and Dutton [Fibonacci Q., \(31 (1993), no. 2, 98-104]\).

In this paper, it is shown that every extended directed triple system of order \(v\) can be embedded in an extended directed triple system of order \(n\) for all \(n \geq 2v\). This produces a generalization of the Doyen- Wilson theorem for extended directed triple systems.

A semigraph \(G\) is an ordered pair \((V,X)\) where \(V\) is a non-empty set whose elements are called vertices of \(G\) and \(X\) is a set of \(n\)-tuples (\(n > 2\)), called edges of \(G\), of distinct vertices satisfying the following conditions:

i) any edge \((v_1, v_2, \ldots, v_n)\) of \(G\) is the same as its reverse \((v_n, v_{n-1}, \ldots, v_1)\),and

ii) any two edges have at most one vertex in common.

Two edges are adjacent if they have a common vertex. \(G\) is edge complete if any two edges in \(G\) are adjacent. In this paper, we enumerate the non-isomorphic edge complete \((p,2)\)semigraphs.

Let \(G = (V, E)\) be a graph. A subset \(D \subseteq V\) is called a dominating set for \(G\) if for every \(v \in V – D\), \(v\) is adjacent to some vertex in \(D\). The domination number \(\gamma(G)\) is equal to \(\min \{|D|: D \text{ is a dominating set of } G\}\).

In this paper, we calculate the domination numbers \(\gamma(C_m \times C_n)\) of the product of two cycles \(C_m\) and \(C_n\) of lengths \(m\) and \(n\) for \(m = 5\) and \(n = 3 \mod 5\), also for \(m = 6, 7\) and arbitrary \(n\).

In this paper, we consider a certain second order linear recurrence and then give generating matriees for the sums of positively and negatively subscripted terms of this recurrence. Further, we use matrix methods and derive explicit. formulas for these sums.

For a simple and finite graph \(G = (V,E)\), let \(w_{\max}(G)\) be the maximum total weight \(w(E) = \sum_{e\in E} w(e)\) of \(G\) over all weight functions \(w: E \to \{-1,1\}\) such that \(G\) has no positive cut, i.e., all cuts \(C\) satisfy \(w(C) \leq 0\).

For \(r \geq 1\), we prove that \(w_{\max}(G) \leq -\frac{|V|}{2}\) if \(G\) is \((2r-1)\)-regular and \(w_{\max}(G) \leq -\frac{r|V|}{2r+1}\) if \(G\) is \(2r\)-regular. We conjecture the existence of a constant \(c\) such that \(w_{\max}(G) \leq -\frac{5|V|}{6} + c\) if \(G\) is a connected cubic graph and prove a special case of this conjecture. Furthermore, as a weakened version of this conjecture, we prove that \(w_{\max}(G) \leq -\frac{2|V|}{3}+\frac{2}{3}\) if \(G\) is a connected cubic graph.

Let \(G_i\) be the subgraph of \(G\) whose edges are in the \(i\)-th color in an \(r\)-coloring of the edges of \(G\). If there exists an \(r\)-coloring of the edges of \(G\) such that \(H_i \nsubseteq G_i\) for all \(1 \leq i \leq r\), then \(G\) is said to be \(r\)-colorable to \((H_1, H_2, \ldots, H_r)\). The multicolor Ramsey number \(R(H_1, H_2, \ldots, H_r)\) is the smallest integer \(n\) such that \(K_n\) is not \(r\)-colorable to \((H_1, H_2, \ldots, H_r)\). It is well known that \(R(C_m, C_4, C_4) = m + 2\) for sufficiently large \(m\). In this paper, we determine the values of \(R(C_m, C_4, C_4)\) for \(m \geq 5\), which show that \(R(C_m, C_4, C_4) = m + 2\) for \(m \geq 11\).