Only the rotational tournament \(U_n\) for odd \(n \geq 5\), has the cycle \(C_n\) as its domination graph. To include an internal chord in \(C_n\), it is necessary for one or more arcs to be added to \(U_n\), in order to create the extended tournament \(U_n^+\). From this, the domination graph of \(U_t\), \(dom(U_n^+)\), may be constructed where \(C_k\), \(3 \leq k \leq n\), is a subgraph of \(dom(U_n^+)\). This paper explores the characteristics of the arcs added to \(U_n\) that are required to create an internal chord in \(C_n\).

In Algebraic Graph Theory, Biggs \([2]\) gives a method for finding the chromatic polynomial of any connected graph by computing the Tutte polynomial. It is used by Biggs \([2]\) to compute the chromatic polynomial of Peterson’s graph. In \(1972\) Sands \([4]\) developed a computer algorithm using matrix operations on the incidence matrix to compute the Tutte Polynomial. In \([1]\), Anthony finds the worst-case time-complexity of computing the Tutte Polynomial. This paper shows a method using group-theoretical properties to compute the Tutte polynomial for Cayley graphs which improves the time-complexity.

Let \(N({Z})\) denote the set of all positive integers (integers). The sum graph \(G_S\) of a finite subset \(S \subset N({Z})\) is the graph \((S, E)\) with \(uv \in E\) if and only if \(u+v \in S\). A graph \(G\) is said to be an (integral) sum graph if it is isomorphic to the sum graph of some \(S \subset N({Z})\). The (integral) sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices which when added to \(G\) result in an (integral) sum graph. A mod (integral) sum graph is a sum graph with \(S \subset {Z}_m \setminus \{0\}\) (\(S \subset {Z}_m\)) and all arithmetic performed modulo \(m\) where \(m \geq |S|+1\) (\(m \geq |S|\)). The mod (integral) sum number \(\rho(G)\) of \(G\) is the least number \(\rho\) (\(\psi\)) of isolated vertices \(\rho K_1\) (\(\psi K_1\)) such that \(G \cup \rho K_1\) (\(G \cup \psi K_1\)) is a mod (integral) sum graph. In this paper, the mod (integral) sum numbers of \(K_{r,s}\) and \(K_n – E(K_r)\) are investigated and bounded, and \(n\)-spoked wheel \(W_n\) is shown to be a mod integral sum graph.

In this paper, the forcing domination numbers of the graphs \(P_n \times P_3\) and \(C_n \times P_3\) are completely determined. This improves the previous results on the forcing domination numbers of \(P_n \times P_2\) and \(C_n \times P_2\).

The stabilizers of the minimum-weight codewords of the binary codes obtained from the strongly regular graphs \(T(n)\) defined by the primitive rank-\(3\) action of the alternating groups \(A_n\), where \(n \geq 5\), on \(\Omega^{(2)}\), the set of duads of \(\Omega = \{1,2,\ldots,n\}\) are examined. For a codeword \(w\) of minimum-weight in the binary code \(C\) obtained as stated above, from an adjacency matrix of the triangular graph \(T(n)\) defined by the primitive rank-3 action of the alternating groups \(A_n\) where \(n \geq 5\), on \(\Omega^{(2)}\), the set of duads of \(\Omega = \{1,2,\ldots,n\}\), we determine the stabilizer \(Aut(C)_w\) in \(Aut(C)\) and show that \(Aut(C)_w\) is a maximal subgroup of \(Aut(C)\).

For a graph \(G\), let \(\mathcal{D}(G)\) be the set of strong orientations of \(G\). Define \(\overrightarrow{d}(G) = \min\{d(D) \mid D \in \mathcal{D}(G)\}\) and \(\rho(G) = \overrightarrow{d}(G) – d(G)\), where \(d(D)\) (resp. \(d(G)\)) denotes the diameter of the digraph \(D\) (resp. graph \(G\)). In this paper, we determine the exact value of \(\rho(K_r \times K_s)\) for \(r \leq s\) and \((r,s) \not\in \{(3,5), (3,6), (4,4)\}\), where \(K_r \times K_s\) denotes the tensor product of \(K_r\) and \(K_s\). Using the results obtained here, a known result on \(\rho(G)\), where \(G\) is a regular complete multipartite graph is deduced as corollary.

A two-step approach to finding knight covers for an \(N \times N\) chessboard eliminates the problem of detecting duplicate partial solutions. The time and storage needed to generate solutions is greatly reduced. The method can handle boards as large as \(45 \times 45\) and has matched or beaten all previously known solutions for every board size tried.

In this paper we prove that there exists a strong critical set of size \(m\) in the back circulant latin square of order \(n\) for all \(\frac{n^2-1}{2} \leq m \leq \frac{n^2-n}{2}\), when \(n\) is odd. Moreover, when \(n\) is even we prove that there exists a strong critical set of size \(m\) in the back circulant latin square of order \(n\) for all \(\frac{n^2-n}{2}-(n-2) \leq m \leq \frac{n^2-n}{2}\) and \(m \in \{\frac{n^2}{4}, \frac{n^2}{4}+2, \frac{n^2}{4}+4, \ldots, \frac{n^2-n}{2}-n\}\).

In this paper, a characterization of two classes of \((q, q+1)\)-geometries, that are fully embedded in a projective space \(PG(n, q)\), is obtained. The first class is the one of the \((q,q+1)\)-geometry \(H^{n,m}_q\), having points the points of \(PG(n, q)\) that are not contained in an \(m\)-dimensional subspace \(\Pi[m]\) of \(PG(n, q)\), for \(0 \leq m \leq n-3\), and lines the lines of \(PG(n, q)\) skew to \(\Pi[m]\). The second class is the one of the \((q,q+1)\)-geometry \(SH^{n,m}_q\), having the same point set as \(H^{n,m}_q\), but with \(-1 \leq m \leq n-3\), and lines the lines skew to \(\Pi^{n,m}_q\) that are not contained in a certain partition of the point set of \(SH^{n,m}_q\). Our characterization uses the axiom of Pasch, which is also known as axiom of Veblen-Young. It is a generalization of the characterization for partial geometries satisfying the axiom of Pasch by J. A. Thas and F. De Clerck. A characterization for \(H^{n,m}_q\) was already proved by H. Cuypers. His result however does not include \(SH^{n,m}_q\).

In this note we construct nested partially balanced incomplete block designs based on \(NC_{m}\)-scheme. Secondly we construct NPBIB designs from a given PBIB design with \(\lambda_{1} = 1\) and \(\lambda_{2} = 0\) with same association scheme for both systems of PBIB designs. Finally, we give some results and examples where the two systems of PBIB designs in NPBIB designs have different association schemes.

This paper discusses the covering property and the Uniqueness Property of Minima (UPM) for linear forms in an arbitrary number of variables, with emphasis on the case of three variables (triple loop graph). It also studies the diameter of some families of undirected chordal ring graphs. We focus upon maximizing the number of vertices in the graph for given diameter and degree. We study the result in \([2]\), we find that the family of triple loop graphs of the form \(G(4k^2+2k+1; 1;2k+1; 2k^2)\) has a larger number of nodes for diameter \(k\) than the family \(G(3k^2+3k+1;1;3k+1;3k+2)\) given in \([2]\). Moreover, we show that both families have the Uniqueness Property of Minima.

In this paper, an algorithm based on. trades is presented to classify two classes of large sets of \(t\)-designs, namely \(LS[14](2, 5, 10)\) and \(LS[6](3, 5, 12)\).

In this work, we study which tubular surfaces verify that the embeddings of infinite, locally finite connected graphs without vertex accumulation points are embeddings without edge accumulation points. Furthermore, we characterize the graphs which admit embeddings with no edge accumulation points in the sphere with \(n\) ends in terms of forbidden subgraphs.

In this paper, self-centered, bi-eccentric splitting graphs are characterized. Further various bounds for domination number, global domination number and the neighborhood number of these graphs are obtained.

In this study we are going to give a new \((t,k)\)-geodetic set definition. This is a refinement of the geodetic set definition given in \([11]\). With this new definition we obtain more information about the graph. We also give a relationship between the \((t,k)\)-geodetic set and the integrity of a graph. By using a \((t,k)\)-geodetic set we give a new proof for the upper bound of integrity of trees and unicycle graphs.

For a long time we had thought that there does not exist an OGDD of type \(4^4\). In this article, an OGDD of type \(4^4\) will be constructed.

Consider a tree \(T = (V, E)\) with root \(r \in V\) and \(|V| = N\). Let \(p_v\) be the probability that a user wants to access node \(v\). A bookmark is an additional link from \(r\) to any other node of \(T\). We want to add \(k\) bookmarks to \(T\), so as to minimize the expected access cost from \(r\), measured by the average length of the shortest path. We present a characterization of an optimal assignment of \(k\) bookmarks in a perfect binary tree with uniform probability distribution of access and \(k \leq \sqrt{N + 1}\).

We show various combinatorial identities that are generated by tree counting arguments. In particular, we give formulas for \(n^p\) and \(\tau(K_{s,t})\) which establishes an equivalence.

The question of necessary and sufficient conditions for the existence of a simple \(3\)-uniform hypergraph with a given degree sequence is a long outstanding open question. We provide a result on degree sequences of \(3\)-hypergraphs which shows that any two \(3\)-hypergraphs with the same degree sequence can be transformed into each other using a sequence of trades, also known as null-\(3\)-hypergraphs. This result is similar to the Havel-Hakimi theorem for degree sequences of graphs.

In this paper we consider the problem as follows: Given a bipartite graph \(G = (V_1, V_2; E)\) with \(|V_1| = |V_2| = n\) and a positive integer \(k\), what degree condition is sufficient to ensure that for any \(k\) distinct vertices \(v_1, v_2, \ldots, v_k\) of \(G\), \(G\) contains \(k\) independent quadrilaterals \(Q_1, Q_2, \ldots, Q_k\) such that \(v_i \in V(Q_i)\) for every \(i \in \{1, 2, \ldots, k\}\), or \(G\) has a \(2\)-factor with \(k\) independent cycles of specified lengths with respect to \(\{v_1, v_2, \ldots, v_k\}\)? We will prove that if \(d(x) + d(y) \geq \left\lceil (4n + k)/3 \right\rceil\) for each pair of nonadjacent vertices \(x \in V_1\) and \(y \in V_2\), then, for any \(k\) distinct vertices \(v_1, v_2, \ldots, v_k\) of \(G\), \(G\) contains \(k\) independent quadrilaterals \(Q_1, Q_2, \ldots, Q_k\) such that \(v_i \in V(Q_i)\) for each \(i \in \{1, \ldots, k\}\). Moreover, \(G\) has a \(2\)-factor with \(k\) cycles with respect to \(\{v_1, v_2, \ldots, v_k\}\) such that \(k – 1\) of them are quadrilaterals. We also discuss the degree conditions in the above results.

We call the graph \(G\) an edge \(m\)-coloured if its edges are coloured with \(m\) colours. A path (or a cycle) is called monochromatic if all its edges are coloured alike. A subset \(S \subseteq V(G)\) is independent by monochromatic paths if for every pair of different vertices from \(S\) there is no monochromatic path between them. In \([5]\) it was defined the Fibonacci number of a graph to be the number of all independent sets of \(G\); recall that \(S\) is independent if no two of its vertices are adjacent. In this paper we define the concept of a monochromatic Fibonacci number of a graph which gives the total number of monochromatic independent sets of \(G\). Moreover we give the number of all independent by monochromatic paths sets of generalized lexicographic product of graphs using the concept of a monochromatic Fibonacci polynomial of a graph. These results generalize the Fibonacci number of a graph and the Fibonacci polynomial of a graph.

Let \(D = (V, E)\) be a primitive digraph. The exponent of \(D\) at a vertex \(u \in V\), denoted by \(\exp_D(u)\), is defined to be the least integer \(k\) such that there is a walk of length \(k\) from \(u\) to \(v\) for each \(v \in V\). Let \(V = \{v_1, v_2, \ldots, v_n\}\). The vertices of \(V\) can be ordered so that \(\exp_D(v_{i_1}) \leq \exp_D(v_{i_2}) \leq \ldots \leq \exp_D(v_{i_n}) = \gamma(D)\). The number \(\exp_p(v_n)\) is called the \(k\)-exponent of \(D\), denoted by \(\exp_p(k)\). We use \(L(D)\) to denote the set of distinct lengths of the cycles of \(D\). In this paper, we completely determine the \(1\)-exponent sets of primitive, minimally strong digraphs with \(n\) vertices and \(L(D) = \{p, q\}\), where \(3 \le p < q\) and \(p + q > n\).

Let \(\mathcal{C}\) be any class of finite graphs. A graph \(G\) is \(\mathcal{C}\)-ultrahomogeneous if every isomorphism between induced subgraphs belonging to \(\mathcal{C}\) extends to an automorphism of \(G\). We study finite graphs that are \({K}_*\)-ultrahomogeneous, where \({K}_*\) is the class of complete graphs. We also explicitly classify the finite graphs that are \(\sqcup{K}_{*}\)-ultrahomogeneous, where \(\sqcup{K}_{*}\) is the class of disjoint unions of complete graphs.

For any positive integer \(n\), let \(S_n\), denote the set of all permutations of the set \(\{1,2,\ldots,n\}\). We think of a permutation just as an ordered list. For any \(p\) in \(S_n\), and for any \(i \leq n\), let \(p \downarrow i\) be the permutation on the set \(\{1,2,\ldots,n – 1\}\) obtained from \(p\) as follows: delete \(i\) from \(p\) and then subtract \(1\) in place from each of the remaining entries of \(p\) which are larger than \(i\). For any \(p\) in \(S_n\), we let \(R(p) = \{q \in S_{n-1} : g = p \downarrow i \;\text{for some} \;i \leq n\}\), the set of reductions of \(p\). It is shown that, for \(n > 4\), any \(p\) in \(S_n\), is determined by its set of reductions \(R(p)\).

For any \(h \in \mathbb{N}\), a graph \(G = (V, E)\) is said to be \(h\)-magic if there exists a labeling \(l: E(G) \to \mathbb{Z}_h – \{0\}\) such that the induced vertex set labeling \(l^+: V(G) \to \mathbb{Z}_h\), defined by

\[l^+(v) = \sum\limits_{uv \in E(G)} l(uv)\]

is a constant map. When this constant is \(0\) we call \(G\) a zero-sum \(h\)-magic graph. The null set of \(G\) is the set of all natural numbers \(h \in \mathbb{N}\) for which \(G\) admits a zero-sum \(h\)-magic labeling. In this paper we will identify several classes of zero sum magic graphs and will determine their null sets.

There are networks that can be modeled by simple graphs, where edges are perfectly reliable but nodes are subject to failure, e.g. hardwired computer systems. One measure of the “vulnerability” of the network is the connectivity \(\kappa\) of the graph. Another, somewhat related, vulnerability parameter is the component order connectivity \(\kappa_c^{(k)}\), i.e. the smallest number of nodes that must fail in order to ensure that all remaining components have order less than some value \(k\). In this paper we present necessary and sufficient conditions on a 4-tuple \((n,k,a,b)\) for a graph \(G\) to exist having \(n\) nodes, \(\kappa = a\), and \(\kappa_c^{(k)} = b\). Sufficiency of the conditions follows from a specific construction described in our work. Using this construction we obtain ranges of values for the number of edges in a graph having \(n\) nodes, \(\kappa = a\), and \(\kappa_c^{(k)} = b\) thereby obtaining sufficient conditions on the \(5\)-tuple \((n,e,k,a,b)\) for a graph to exist having \(n\) nodes, \(e\) edges, \(\kappa = a\), and \(\kappa_c^{(k)} = b\). In a limited number of special cases, we show the conditions on \((n,e,k,a,b)\) to be necessary as well.