A transitive triple, \((a, b, c)\), is defined to be the set \(\{(a, b), (b, c), (a, c)\}\) of ordered pairs. A directed triple system of order \(v\), \(DTS(v)\), is a pair \((D, \beta)\), where \(D\) is a set of \(v\) points and \(\beta\) is a collection of transitive triples of pairwise distinct points of \(D\) such that any ordered pair of distinct points of \(D\) is contained in precisely one transitive triple of \(\beta\). An antiautomorphism of a directed triple system, \((D, \beta)\), is a permutation of \(D\) which maps \(\beta\) to \(\beta^{-1}\), where \(\beta^{-1} = \{(c, b, a) | (a, b, c) \in \beta\}\). In this paper, we give necessary and sufficient conditions for the existence of a directed triple system of order \(v\) admitting an antiautomorphism consisting of two cycles of lengths \(M\) and \(2M\), and one fixed point.

A \(k\)-circuit is a directed cycle of length \(k\). In this paper, we completely solve the problem of finding maximum packings and minimum coverings of \(\lambda\)-fold complete bipartite symmetric digraphs with \(6\)-circuits.

Until now, all known simple \(t-(v, k, \lambda)\) designs with \(t \geq 6\) have \(\lambda \geq 4\). On the other hand, P. J. Cameron and C. E. Praeger showed that there are no flag-transitive simple \(7-(v, k, \lambda)\) designs. In the present paper, we considered the flag-transitive simple \(6-(v, k, \lambda)\) designs and proved that there are no non-trivial flag-transitive simple \(6-(v, k, \lambda)\) designs with \(\lambda \leq 5\).

In \(1972\), Erdős, Faber, and Lovász made the now famous conjecture: If a graph \(G\) consists of \(n\) copies of the complete graph \(K_n\), such that any two copies have at most one common vertex (such graphs are called EFL graphs), then \(G\) is \(n\)-colorable. In this paper, we show that the conjecture is true for two different classes of EFL graphs. Furthermore, a new shorter proof of the conjecture is given for a third class of EFL graphs.

The edge set of \(K_n\) cannot be decomposed into edge-disjoint octagons (or \(8\)-cycles) when \(n \not\equiv 1 \pmod{16}\). We consider the problem of removing edges from the edge set of \(K_n\) so that the remaining graph can be decomposed into edge-disjoint octagons. This paper gives the solution of finding maximum packings of complete graphs with edge-disjoint octagons and the minimum leaves are given.

In this paper, we introduced the notion of symmetric \(f\) bi-derivations on lattices and investigated some related properties. We characterized the distributive lattice by symmetric \(f\) bi-derivations.

In \(1990\), Anderson et al. \([1]\) generalized the competition graph of a digraph to the competition multigraph of a digraph and defined the multicompetition number of a multigraph. The competition multigraph \(CM(D)\) of a digraph \(D = (V, A)\) is the multigraph \(M = (V, E’)\) where two vertices of \(V\) are joined by \(k\) parallel edges if and only if they have exactly \(\ell\) common preys in \(D\). The multicompetition number \(k^*(M)\) of the multigraph \(M\) is the minimum number \(p\) such that \(M \cup I_p\) is the competition multigraph of an acyclic digraph, where \(I_k\) is a set of \(p\) isolated vertices. In this paper, we study the multicompetition numbers for some multigraphs and generalize some results provided by Kim and Roberts \([9]\), and by Zhao and He \([18]\) on general competition graphs, respectively.

Frank Harary contributed numerous questions to a variety of topics in graph theory. One of his favourite topics was the Reconstruction Problem, which, in its first issue in \(1977\), the Journal of Graph Theory described as the major unsolved problem in the field. Together with Plantholt, Frank Harary initiated the study of reconstruction numbers of graphs. We shall here present a survey of some of the work done on reconstruction numbers, focusing mainly on the questions which this work leaves open.

An upper bound of the basis number of the lexicographic product of two graphs from the basis number of the factors is presented. Furthermore, the basis numbers of the lexicographic product of some classes of graphs is determined.

In this paper, we prove that for any graph \(G\), \(\lambda(G^{+++}) = \delta(G^{-++})\) and all but for a few exceptions, \(G^{-++}\) is super edge-connectivity where \(G^{-++}\) is the transformation graph of a graph \(G\) introduced in \([1]\).

A graph-pair of order \(t\) is two non-isomorphic graphs \(G\) and \(H\) on \(t\) non-isolated vertices for which \(G \cup H \cong K_t\) for some integer \(t \geq 4\). Given a graph-pair \((G,H)\), we say \((G, H)\) divides some graph \(K\) if the edges of \(K\) can be partitioned into copies of \(G\) and \(H\) with at least one copy of \(G\) and at least one copy of \(H\). We will refer to this partition as a \((G, H)\)-\(multidecomposition\) of \(K\).

In this paper, we consider the existence of multidecompositions of \(K_n – F\) into graph-pairs of order \(5\) where \(F\) is a Hamiltonian cycle or (almost) \(1\)-factor.

The upper chromatic number \(\overline{\chi}_u(\mathcal{H})\) of a \(C\)-hypergraph \(\mathcal{H} = (X, C)\) is the maximum number of colors that can be assigned to the vertices of \(\mathcal{H}\) in such a way that each \(C \in \mathcal{C}\) contains at least a monochromatic pair of vertices. This paper gives an upper bound for the upper chromatic number of Steiner triple systems of order \(n\) and proves that it is best possible for any \(n (\equiv 1 \text{ or } 3 \pmod{6})\).

A map is called Unicursal if it has exactly two vertices of odd valency. A near-triangulation is a map with all but one of its faces triangles. We use the enufunction approach to enumerate rooted Unicursal planar near-triangulations with the valency of the root-face and the number of non-rooted faces as parameters.

An edge coloring is proper if no two adjacent edges are assigned the same color and vertex-distinguishing proper coloring if it is proper and incident edge sets of every two distinct vertices are assigned different sets of colors. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph \(G\) is denoted by \(\overline{\chi}'(G)\). In this paper, we prove that \(\overline{\chi}'(G) \leq \Delta(G) + {4}\) if \(G = (V, E)\) is a connected graph of order \(n \geq 3\) and \(\sigma_2(G) \geq n\), where \(\sigma_2(G) = \min\{d(x) + d(y) | xy \in E(G)\}\).

In this paper, we study the minimum distance between the set of bent functions and the set of \(1\)-resilient Boolean functions and present lower bounds on that. The first bound is proved to be tight for functions up to \(10\) input variables and a revised bound is proved to be tight for functions up to \(14\) variables. As a consequence, we present a strategy to modify the bent functions, by toggling some of its outputs, in getting a large class of \(1\)-resilient functions with very good nonlinearity and autocorrelation. In particular, the technique is applied up to \(14\)-variable functions and we show that the construction provides a large class of \(1\)-resilient functions reaching currently best known nonlinearity and achieving very low autocorrelation values which were not known earlier. The technique is sound enough to theoretically solve some of the mysteries of \(8\)-variable, \(1\)-resilient functions with maximum possible nonlinearity. However, the situation becomes complicated from \(10\) variables and above, where we need to go for complicated combinatorial analysis with trial and error using computational facility.

In this paper, we characterize the variety of quasi-groups isotopic to abelian groups by four-variable identities.

A direct method for constructing large sets of \(t\)-designs is based on the concept of assembling orbits of a permutation group \(G\) on \(k\)-subsets of a \(v\)-set into block sets of \(t\)-designs so that these designs form a large set. If \(G\) is \(t\)-homogeneous, then any orbit is a \(t\)-design and therefore we obtain a large set by partitioning the set of orbits into parts consisting of the same number of \(k\)-subsets. In general, it is hard to find such partitions. We solve this problem when orbit sizes are limited to two values. We then use its corollaries to obtain some results in a special case in which a simple divisibility condition holds and no knowledge about orbit sizes is assumed.

Dean \(([3])\) shows that if \(G\) be a \(k\)-connected graph such that any fragment whose neighborhood contains an edge has cardinality exceeding \(\frac{k}{2}\), then the subgraph \(H = (V(G), E_k(G))\) formed by \(V(G)\) and the \(k\)-contractible edges of \(G\) is \(2\)-connected. In this paper, we show that for \(k = 4\), Dean’s result holds when reduced \(\frac{k}{2}\) to \(\frac{k}{4}\). But for \(k \geq 5\), we give a counterexample to show that it is false and give a lower bound of the number of \(k\)-contractible edges for \(k = 5\).

Let \(G\) be a finite simple \(\chi\)-chromatic graph and \(\mathcal{L} = \{L_u\}_{u\in V(G)}\) be a list assignment to its vertices with \(L_u \subseteq \{1,…,\chi\}\). A list colouring problem \((G, \mathcal{L})\) with a unique solution for which the sum \(\sum_{u\in V(G)}|L_u|\) is maximized, is called a \(maximum\; \chi-list \;assignment\) of \(G\). In this paper, we prove a \(Circuit\; Simulation\) Lemma that, strictly speaking, makes it possible to simulate any Boolean function by \(effective\) 3-colourings of a graph that is \(polynomial-time \;constructable\) from the Boolean function itself. We use the lemma to simply prove some old results as corollaries, and also we prove that the following decision problem, related to the computation of the fixing number of a graph [Daneshgar \(1997\), Daneshgar and Naserasr, Ars Combin. \(69\) \((2003)\)], is \(\sum_{2}^{P}\)-complete.

In this paper, we give another proof for labeled spanning forests of the complete bipartite graph \(K_{m,n}\), and obtain two Abel-type polynomials. And then we investigate the enumeration of non-trivial rooted labeled spanning forests of the complete bipartite graph \(K_{m,n}\).

In this paper, we investigate the global behavior of the difference equation

\[x_{n+1} = \frac{\alpha x_{n-k}}{\beta+\gamma x_{n-(k+1)}^p},\text{n=1,2,}\ldots\]

with non-negative parameters and non-negative initial conditions, where \(k\) is an odd number.

In many papers, the relation between the domination number of a product of graphs and the product of domination numbers of factors is studied. Here we investigate this problem for domination and total domination numbers in the cross product of digraphs. We give analogues of known results for graphs, and we also present new results for digraphs with sources. Using these results, we find domination (total domination) numbers for some classes of digraphs.

Let \(P_{k+1}\) denote a path of length \(k\) and let \(C_k\) denote a cycle of length \(k\). As usual, \(K_n\) denotes the complete graph on \(n\) vertices. In this paper, we investigate decompositions of \(K_n\) into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing \(K_n\) into \(p\) copies of \(P_5\) and \(q\) copies of \(C_4\) for all possible values of \(p\geq 0\) and \(q\geq 0\).

Given a simple connected undirected graph \(G\), the Wiener index \(W(G)\) of \(G\) is defined as half the sum of the distances over all pairs of vertices of \(G\). In practice, \(G\) corresponds to what is known as the molecular graph of an organic compound. We obtain a sharp lower bound for \(W(G)\) of an arbitrary graph in terms of the order, size, and diameter of \(G\).

The Zagreb indices are topological indices of graphs, which are defined as:\(M_1(G) = \sum\limits_{v \in V(G)} (d(v))^2\), \(M_2(G) = \sum\limits_{uv \in E(G)} d(u)d(v)\) .In this paper, we determine the upper and lower bounds for the Zagreb indices of unicyclic graphs in terms of their order and girth. In each case, we characterize the extremal graphs.

In this paper, we are concerned with Leibniz numbers. We establish a series of identities involving Leibniz numbers, Stirling numbers, harmonic numbers, arctan numbers by making use of generating functions. In addition, we give the asymptotic expansion of certain sums related to Leibniz numbers by Laplace’s method.

We consider the undirected simple connected graph for which edges fail independently of each other with equal probability \(1 – p\) and nodes are perfect. The all-terminal reliability of a graph \(G\) is the probability that the spanning subgraph of surviving edges is connected, denoted as \(R(G,p)\). Graph \(G \in \Omega(n,e)\) is said to be uniformly least reliable if \(R(G,p) \leq R(G’,p)\) for all \(G’ \in \Omega(n,e)\), and for all edge failure probabilities \(0 < 1 – p < 1\). In this paper, we prove the existence of uniformly least reliable graphs in the class \(\Omega(n,e)\) for \(e \leq n + 1\) and give their topologies.

We study V- and \(\Lambda\)-patterns which generalize valleys and peaks, as well as increasing and decreasing runs, in permutations. A complete classification of permutations (multi)-avoiding V- and \(\Lambda\)-patterns of length \(4\) is given. We also establish a connection between restricted permutations and matchings in the coronas of complete graphs.

Let \(G\) be a connected graph. A weakly connected dominating set of \(G\) is a dominating set \(D\) such that the edges not incident to any vertex in \(D\) do not separate the graph \(G\). In this paper, we first consider the relationship between weakly connected domination number \(\gamma_w(G)\) and the irredundance number \(ir(G)\). We prove that \(\gamma_w(G) \leq \frac{5}{2}ir(G) – 2\) and this bound is sharp. Furthermore, for a tree \(T\), we give a sufficient and necessary condition for \(\gamma_c(T) = \gamma_w(T) + k\), where \(\gamma_c(T)\) is the connected domination number and \(0 \leq k \leq \gamma_w(T) – 1\).

For two vertices \(u\) and \(v\) in a strong digraph \(D\), the strong distance \(sd(u,v)\) between \(u\) and \(v\) is the minimum size (the number of arcs) of a strong sub-digraph of \(D\) containing \(u\) and \(v\). The strong eccentricity \(se(v)\) of a vertex \(v\) of \(D\) is the strong distance between \(v\) and a vertex farthest from \(v\). The strong radius \(srad(D)\) (resp. strong diameter \(sdiam(D)\)) of \(D\) is the minimum (resp. maximum) strong eccentricity among all vertices of \(D\). The lower (resp. upper) orientable strong radius \(srad(G)\) (resp. \(SRAD(G)\)) of a graph \(G\) is the minimum (resp. maximum) strong radius over all strong orientations of \(G\). The lower (resp. upper) orientable strong diameter \(sdiam(G)\) (resp. \(SDIAM(G)\)) of a graph \(G\) is the minimum (resp. maximum) strong diameter over all strong orientations of \(G\). In this paper, we determine the lower orientable strong radius and strong diameter of the Cartesian product of complete graphs, and give the upper orientable strong diameter and the bounds on the upper orientable strong radius of the Cartesian product of complete graphs.

In this paper, we show that the disjoint union of two cordial graphs, one of them is of even size, is cordial and the join of two cordial graphs, both are of even size or one of them is of even size and one of them is of even order, is cordial. We also show that \(C_m \cup C_n \) is cordial if and only if \(m+n \not\equiv 2 \pmod{4}\) and \(mC_n\) is cordial if and only if \(mn \not\equiv 2 \pmod{4}\) and for \(m, n \geq 3\), \(C_m + C_n\) is cordial if and only if \((m, n) \neq (3, 3)\) and \(\{m, n\} \not\equiv \{0, 2\} \pmod{4}\).

Finally, we discuss the cordiality of \(P_n^k\).

We show that a finite linear space with \(b = n^2 + n + 1\) lines, \(n \geq 2\), constant point-degree \(n+1\) and containing a sufficient number of lines of size \(n\) can be embedded in a projective plane of order \(n\). Using this fact, we also give characterizations of some pseudo-complements, which are the complements of certain subsets of finite projective planes.

The numbers of distinct self-orthogonal Latin squares (SOLS) and idempotent SOLS have been enumerated for orders up to and including $9$. The isomorphism classes of idempotent SOLS have also been enumerated for these orders. However, the enumeration of the isomorphism classes of non-idempotent SOLS is still an open problem. By utilising the automorphism groups of class representatives from the already enumerated isomorphism classes of idempotent SOLS, we enumerate the isomorphism classes of non-idempotent SOLS implicitly (i.e. without generating them). New symmetry classes of SOLS are also introduced, based on the number of allowable transformations that may be applied to a SOLS without destroying the property of self-orthogonality, and these classes are also enumerated.

The supereulerian index of a graph \(G\) is the smallest integer \(k\) such that the \(k\)-th iterated line graph of \(G\) is supereulerian. We first show that adding an edge between two vertices with degree sums at least three in a graph cannot increase its supereulerian index. We use this result to prove that the supereulerian index of a graph \(G\) will not be changed after either of contracting an \(A_G(F)\)-contractible subgraph \(F\) of a graph \(G\) and performing the closure operation on \(G\) (if \(G\) is claw-free). Our results extend Catlin’s remarkable theorem \([4]\) relating that the supereulericity of a graph is stable under the contraction of a collapsible subgraph.

This paper is based on the splitting operation for binary matroids that was introduced by Raghunathan, Shikare and Waphare [ Discrete Math. \(184 (1998)\), p.\(267-271\)] as a natural generalization of the corresponding operation in graphs. Here, we consider the problem of determining precisely which graphs \(G\) have the property that the splitting operation, by every pair of edges, on the cycle matroid \(M(G)\) yields a graphic matroid. This problem is solved by proving that there are exactly four minor-minimal graphs that do not have this property.

In this paper, we study the connection of number theory with graph theory via investigating some uncharted properties of the directed graph \(\Gamma'(n)\) whose vertex set is \(\mathbb{Z}_n = \{0,1,\ldots,n-1\}\), and for which there is a directed edge from \(a \in \mathbb{Z}_n\) to \(b \in \mathbb{Z}_n\) if and only if \(a^3 \equiv b \pmod{n}\). For an arbitrary prime \(p\), the formula for the decomposition of the graph \(\Gamma(p)\) is established. We specify two subgraphs \(\Gamma_1(n)\) and \(\Gamma_2(n)\) of \(\Gamma(n)\). Let \(\Gamma_1(n)\) be induced by the vertices which are coprime to \(n\) and \(\Gamma_2(n)\) by induced by the set of vertices which are not coprime to \(n\). We determine the level of every component of \(\Gamma_1(n)\), and establish necessary and sufficient conditions when \(\Gamma_1(n)\) or \(\Gamma_2(n)\) has no cycles with length greater than \(1\), respectively. Moreover, the conditions for the semiregularity of \(\Gamma_2(n)\) are presented.

We made a computer search for minimal blocking sets in the projective geometry \(\text{PG}(2,11)\), and found \(30,000\), of which only two nontrivial blocking sets had the possibility of being isomorphic.

A graph \(G\) is called \({claw-free}\) if \(G\) has no induced subgraph isomorphic to \(K_{1,3}\). Ando et al. obtained the result: a claw-free graph \(G\) with minimum degree at least \(d\) has a path-factor such that the order of each path is at least \(d+1\); in particular \(G\) has a \(\{P_3, P_4, P_5\}\)-factor whenever \(d \geq 2\). Kawarabayashi et al. proved that every \(2\)-connected cubic graph has a \(\{P_3, P_4\}\)-factor. In this article, we show that if \(G\) is a connected claw-free graph with at least \(6\) vertices and minimum degree at least \(2\), then \(G\) has a \(\{P_3, P_4\}\)-factor. As an immediate consequence, it follows that every claw-free cubic graph (not necessarily connected) has a \(\{P_3, P_4\}\)-factor.

In this paper, we study the combinatorial properties of \(w\)-IPP (identifiable parents property) codes and give necessary and sufficient conditions for a code to be a \(w\)-IPP code. Furthermore, let \(R(C) = \frac{1}{n}{\log_q|C|}\) denote the rate of the \(q\)-ary code \(C\) of length \(n\), suppose \(q \geq 3\) is a prime power, we prove that there exists a sequence of linear \(q\)-ary \(2\)-IPP codes \(C_n\) of length \(n\) with \(R(C_n) = \frac{1}{3}log\frac{q^3}{4q^2-6q+3}\).

Let \(P(G,\lambda)\) be the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are said to be chromatically equivalent, denoted \(G \sim H\), if \(P(G,\lambda) = P(H,\lambda)\). We write \([G] = \{H | H \sim G\}\). If \([G] = \{G\}\), then \(G\) is said to be chromatically unique. In this paper, we first characterize certain complete tripartite graphs \(G\) according to the number of \(4\)-independent partitions of \(G\). Using these results, we investigate the chromaticity of \(G\) with certain star or matching deleted. As a by-product, we obtain new families of chromatically unique complete tripartite graphs with certain star or matching deleted.

In this paper, we introduce a hyperoperation associated to the set of all arithmetic functions and analyze the properties of this new hyperoperation. Several characterization theorems are obtained, especially in connection with multiplicative functions.

In this paper, we introduce two new types of labelings of graphs using Fibonacci numbers, namely, Fibonacci graceful labelings and Super Fibonacci graceful labelings. We discuss the existence and non-existence of Fibonacci and Super Fibonacci graceful labelings for certain classes of graphs. Also, we discuss the Fibonacci gracefulness of disjoint union of Super Fibonacci graceful graphs, pendant edge extension of Super Fibonacci graceful graphs, and amalgamation of Super Fibonacci graceful graphs. Finally, we compare the graceful graphs with Fibonacci graceful graphs.

Let the columns of a \(p \times q\) matrix \(M\) over any ring be partitioned into \(n\) blocks, \(M = [M_1, \ldots, M_n]\). If no \(p \times p\) submatrix of \(M\) with columns from distinct blocks \(M_{i}\) is invertible, then there is an invertible \(p \times p\) matrix \(Q\) and a positive integer \(m \leq p\) such that \([QM_1, \ldots, QM_n]\) is in reduced echelon form and in all but at most \(m – 1\) blocks \(QM_i\) the last \(m\) entries of each column are either all zero or they include a non-zero non-unit.

A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) \(G\) with vertex set \(V(G)\) is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex \(x \in V(G)\) such that \(G – x\) is a tree (respectively, forest). In this paper, we determine the largest numbers of maximal independent sets among all quasi-tree graphs and quasi-forest graphs. We also characterize those extremal graphs achieving these values.

In \(2004\), Fischermann et al. \([2]\) generalized bound polysemy to competition polysemy by using digraphs instead of posets. They provided a characterization of competition polysemic pairs and a characterization of the connected graphs \(G\) for which there exists a tree \(T\) such that \((G,T)\) is competition polysemic. In this paper, we continue to study the competition polysemy and characterize the connected graphs \(G\) for which there exists a triangle-free unicyclic graph \(G’\) such that \((G,G’)\) is competition polysemic. Furthermore,we generalize competition polysemy to \(m\)-competition polysemy and
prove a characterization of \(m\)-competition polysemic pairs.

A diagonally switchable \(\lambda\)-fold \(4\)-cycle system of order \(n\), briefly DS4CS\((n, \lambda)\), is a \(\lambda\)-fold \(4\)-cycle system in which by replacing each \(4\)-cycle \((a,b,c,d)\) covering pairs \(ab, bc, cd, da\) by either of the \(4\)-cycles \((a,c,b,d)\) or \((a,d,c,b)\) another \(\lambda\)-fold \(4\)-cycle system is obtained. In \([3]\) Adams, Bryant, Grannell, and Griggs proved that a DS4CS\((n, 1)\) exists if and only if \(n \equiv 1 \pmod{8}\), \(n \geq 17\) with the possible exception of \(n = 17\). In this paper we prove that for \(\lambda \geq 2\) the necessary conditions for the existence of a \(A\)-fold \(4\)-cycle system of order \(7\) are also sufficient for the existence of a DS4CS\((n, \lambda)\) except for \((n, \lambda) = (5, 2)\).

Let \(G\) be a graph. Let \(g(x)\) and \(f(x)\) be two nonnegative integer-valued functions defined on \(V(G)\) with \(g(x) \leq f(x)\) for any \(x \in V(G)\). A spanning subgraph \(F\) of \(G\) is called a fractional \((g, f)\)-factor if \(g(x) \leq d_G^h(x) \leq f(x)\) for all \(x \in V(G)\), where \(d_G^h(x) = \sum_{e \in E_x} h(e)\) is the fractional degree of \(x \in V(F)\) with \(E_x = \{e : e = xy \in E(G)\}\). A graph \(G\) is said to be fractional \((g, f, n)\)-critical if \(G – N\) has a fractional \((g, f)\)-factor for each \(N \subseteq V(G)\) with \(|N| = n\). In this paper, several sufficient conditions in terms of stability number and degree for graphs to be fractional \((g, f, n)\)-critical are given. Moreover, we show that the results in this paper are best possible in some sense.