Let \(G = (V,E)\) be a graph. A set \(S \subseteq V\) is a dominating set of \(G\) if every vertex not in \(S\) is adjacent to some vertex in \(S\). The domination number of \(G\), denoted by \(\gamma(G)\), is the minimum cardinality of a dominating set of \(G\). A set \(S \subseteq V\) is a total dominating set of \(G\) if every vertex of \(V\) is adjacent to some vertex in \(S\). The total domination number of \(G\), denoted by \(\gamma_t(G)\), is the minimum cardinality of a total dominating set of \(G\). In this paper, we provide a constructive characterization of those trees with equal domination and total domination numbers.
We consider a variation of a classical Turán-type extremal problem due to Bollobás \([2,p. 398, no. 13]\) as follows: determine the smallest even integer \(\sigma(C^k,n)\) such that every graphic sequence \(\pi = (d_1,d_2,\ldots,d_n)\) with term sum \(\sigma(\pi) = d_1 + d_2 + \cdots + d_n \geq \sigma(C^k,n)\) has a realization \(G\) containing a cycle with \(k\) chords incident to a vertex on the cycle. Moreover, we also consider a variation of a classical Turán-type extremal result due to Faudree and Schelp \([7]\) as follows: determine the smallest even integer \(\sigma(P_\ell,n)\) such that every graphic sequence \(\pi = (d_1,d_2,\ldots,d_n)\) with \(\sigma(\pi) \geq \sigma(P_\ell,n)\) has a realization \(G\) containing \(P_\ell\) as a subgraph, where \(P_\ell\) is the path of length 2. In this paper, we determine the values of \(\sigma(P_\ell,n)\) for \(n \geq \ell+1\) and the values of \(\sigma(C^k,n)\) for \(n \geq (k+3)(2k+5)\).
The hyperbolic Fibonacci function, which is the continuous extension of Binet’s formula for the Fibonacci number, transforms the Fibonacci number theory into a “continuous” theory because every identity for the hyperbolic Fibonacci function has its discrete analogy in the framework of the Fibonacci number. In this new paper, we define three important generalizations of the \(k\)-Fibonacci sine, cosine, and quasi-sine hyperbolic functions and then carry over many concepts and techniques that we learned in a standard setting for the \(k\)-Fibonacci sine, cosine, and quasi-sine hyperbolic functions to the generalizations of these functions.
A new construction of authentication codes with arbitration from pseudo-symplectic geometry over finite fields is given. The parameters and the probabilities of deceptions of the codes are also computed.
It was conjectured in a recently published paper that for any integer \(k \geq 8\) and any even integer \(n\) with \(2k+3 < n < 2k+\lfloor\frac{k}{2}\rfloor+3\), the \(k\)th power \(C_n^k\) of the \(n\)-cycle is not a divisor graph. In this paper, we prove this conjecture, hence obtaining a complete characterization of those powers of cycles which are divisor graphs.
Inspired by a recent paper by Giulietti, Korchmàros and Torres \([3]\), we provide equations for some quotient curves of the Deligne-Lusztig curve associated to the Suzuki group \(S_z(q)\).
In this paper, we study the global behavior of the nonnegative equilibrium points of the difference equation
\[x_{n+1} = \frac{ax_{n-2l}}{b+c\prod\limits_{i=0}^{k+1}x_{n-2i}}, \quad n=0,1,\ldots,\]
where \(a\), \(b\), and \(c\) are nonnegative parameters, initial conditions are nonnegative real numbers, and \(k\) and \(l\) are nonnegative integers, with \(l \leq k+1\).
The chromatic polynomial of a graph \(\Gamma\), \(C(\Gamma; \lambda)\), is the polynomial in \(\lambda\) which counts the number of distinct proper vertex \(\lambda\)-colorings of \(\Gamma\), given \(\lambda\) colors. By applying the addition-contraction method, chromatic polynomials of some sequences of \(2\)-connected graphs satisfy a number of recursive relations. We will show that by knowing the chromatic polynomial of a few small graphs, the chromatic polynomial of each of these sequences can be computed by utilizing either matrices or generating functions.
An \(f\)-coloring of a graph \(G\) is an edge-coloring of \(G\) such that each color appears at each vertex \(v \in V(G)\) at most \(f(v)\) times. The minimum number of colors needed to \(f\)-color \(G\) is called the \(f\)-chromatic index of \(G\). A simple graph \(G\) is of \(f\)-class 1 if the \(f\)-chromatic index of \(G\) equals \(\Delta_f(G)\), where \(\Delta_f(G) = \max_{v\in V(G)}\{\left\lceil\frac{d(v)}{f(v)}\right\rceil\}\). In this article, we find a new sufficient condition for a simple graph to be of \(f\)-class 1, which is strictly better than a condition presented by Zhang and Liu in 2008 and is sharp. Combining the previous conclusions with this new condition, we improve a result of Zhang and Liu in 2007.
We provide the specifics of how affine planes of orders three, four, and five can be used to partition the full design comprising all triples on \(9, 16\), and \(25\) elements, respectively. Key results of the approach for order five are generalized to reveal when there is potential for using suitable affine planes of order \(n\) to partition the complete sets of \(n^2\) triples into sets of mutually disjoint triples covering either all \(n^2\), or else precisely \(n^2 – 1\), elements.
In this paper, the notion of left-right and right-left \(f\)-derivation of a BCC-algebra is introduced, and some related properties are investigated. Also, we consider regular \(f\)-derivation and \(d\)-invariant on \(f\)-ideals in BCC-algebras.
Let \(G\) be a planar graph with maximum degree \(\Delta\). It’s proved that if \(\Delta \geq 5\) and \(G\) does not contain \(5\)-cycles and \(6\)-cycles, then \(la(G) = \lceil\frac{\Delta(G)}{2}\rceil\).
We call the digraph \(D\) an \(m\)-coloured digraph if the arcs of \(D\) are coloured with \(m\) colours. A subdigraph \(H\) of \(D\) is called monochromatic if all of its arcs are coloured alike.
A set \(N \subseteq V(D)\) is said to be a kernel by monochromatic paths if it satisfies the following two conditions:
(i) For every pair of different vertices \(u,v \in N\) there is no monochromatic directed path between them.
(ii) For every vertex \(x \in V(D) – N\), there is a vertex \(y \in N\) such that there is an \(xy\)-monochromatic directed path.
In this paper, it is proved that if \(D\) is an \(m\)-coloured \(k\)-partite tournament such that every directed cycle of length \(3\) and every directed cycle of length \(4\) is monochromatic, then \(D\) has a kernel by monochromatic paths.
Some previous results are generalized.
Let \(\mathcal{S}\) be a finite family of sets in \(\mathbb{R}^d\), each a finite union of polyhedral sets at the origin and each having the origin as an extreme point. Fix \(d\) and \(k\), \(0 \leq k \leq d \leq 3\). If every \(d+1\) (not necessarily distinct) members of \(\mathcal{S}\) intersect in a star-shaped set whose kernel is at least \(k\)-dimensional, then \(\cap\{S_i:S_i\in\mathcal{S}\}\) also is a star-shaped set whose kernel is at least \(k\)-dimensional. For \(k\neq 0\), the number \(d+1\) is best possible.
A graph is said to be cordial if it has a \(0-1\) labeling that satisfies certain properties. The second power of paths \(P_n^2\),is the graph obtained from the path \(P_n\) by adding edges that join all vertices \(u\) and \(v\) with \(d(u,v) = 2\). In this paper, we show that certain combinations of second power of paths, paths, cycles, and stars are cordial. Specifically, we investigate the cordiality of the join and the union of pairs of second power of paths and graphs consisting of one second power of path and one path and one cycle.
We initiate a study of the toughness of infinite graphs by considering a natural generalization of that for finite graphs. After providing general calculation tools, computations are completed for several examples. Avenues for future study are presented, including existence problems for tough-sets and calculations of maximum possible toughness. Several open problems are posed.
Let an \(H\)-point be a vertex of a tiling of \(\mathbb{R}^2\) by regular hexagons of side length 1, and \(D(n)\) a circle of radius \(n\) (\(n \in \mathbb{Z}^+\)) centered at an \(H\)-point. In this paper, we present an algorithm to calculate the number, \(\mathcal{N}_H(D(n))\), of H-points that lie inside or on the boundary of \(D(n)\). Furthermore, we show that the ratio \(\mathcal{N}_H(D(n))/n^2\) tends to \(\frac{2\pi}{S}\) as \(n\) tends to \(\infty\), where \(S = \frac{3\sqrt{3}}{2}\) is the area of the regular hexagonal tiles.
Let \(G\) be a finite, simple graph. We denote by \(\gamma(G)\) the domination number of \(G\). The bondage number of \(G\), denoted by \(b(G)\), is the minimum number of edges of \(G\) whose removal increases the domination number of \(G\). \(C_n\) denotes the cycle of \(n\) vertices. For \(n \geq 5\) and \(n \neq 5k + 3\), the domination number of \(C_5 \times C_n\) was determined in [6]. In this paper, we calculate the domination number of \(C_5 \times C_n\) for \(n = 5k + 3\) (\(k \geq 1\)), and also study the bondage number of this graph, where \(C_5 \times C_n\) is the cartesian product of \(C_5\) and \(C_n\).
A vertex cut that separates the connected graph into components such that every vertex in these components has at least \(g\) neighbors is an \(R^g\)-vertex-cut. \(R^g\)-vertex-connectivity, denoted by \(\kappa^g(G)\), is the cardinality of a minimum \(R^g\)-vertex-cut of \(G\). In this paper, we will determine \(\kappa^g\) and characterize the \(R^g\)-vertex-atom-part for the first and second type Harary graphs.
A graph \(G\) is supereulerian if \(G\) has a spanning eulerian subgraph. We use \(\mathcal{SL}\) to denote the families of supereulerian graphs. In 1995, Zhi-Hong Chen and Hong-Jian Lai presented the following open problem [2, problem 8.8]: Determine
\[L=\min\max\limits_{G\in SL-\{K_1\}}\{\frac{|E(H)|}{|E(G)|} : H \text{ is spanning eulerian subgroup of G}\}.\]
For a graph \(G\), \(O(G)\) denotes the set of all odd-degree vertices of \(G\). Let \(G\) be a simple graph and \(|O(G)| = 2k\). In this note, we show that if \(G\in{SL}\) and \(k \leq 2\), then \(L \geq \frac{2}{3}\).
It is known that the number of Dyck paths is given by a Catalan number. Dyck paths are represented as plane lattice paths which start at the origin \(O\) and end at the point \(P_n = (n,n)\) repeating \((1,0)\) or \((0,1)\) steps without going above the diagonal line \(OP_n\). Therefore, it is reasonable to ask of any positive integers \(a\) and \(b\) what number of lattice paths start at \(O\) and end at point \(A = (a, b)\) repeating the same steps without going above the diagonal line \(OA\). In this article, we show a formula to represent the number of such generalized Dyck paths.
Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\), and let \(A\) be an abelian group. A labeling \(f : V(G) \to A\) induces an edge labeling \(f^* : E(G) \to A\) defined by \(f^*(xy) = f(x) + f(y)\), for each edge \(xy \in E(G)\). For \(i \in A\), let \(v_f(i) = \mathrm{card}\{v \in V(G) : f(v) = i\}\) and \(e_f(i) = \mathrm{card}\{e \in E(G) : f^*(e) = i\}\). Let \(c(f) = \{|e_f(i) – e_f(j)|: (i, j) \in A \times A\}\). A labeling \(f\) of a graph \(G\) is said to be \(A\)-friendly if \(|v_f(i)- v_f(j)| \leq 1\) for all \((i, j) \in A \times A\). If \(c(f)\) is a \((0, 1)\)-matrix for an \(A\)-friendly labeling \(f\), then \(f\) is said to be \(A\)-cordial. When \(A = \mathbb{Z}_2\), the friendly index set of the graph \(G\), \(FI(G)\), is defined as \(\{|e_f(0) – e_f(1)| : \text{the vertex labeling } f \text{ is } \mathbb{Z}_2\text{-friendly}\}\). In [13] the friendly index set of cycles are completely determined. In this paper we describe the friendly index sets of cycles with parallel chords. We show that for a cycle with an arbitrary non-empty set of parallel chords, the numbers in its friendly index set form an arithmetic progression with common difference 2.
The eccentricity \(e(v)\) of a vertex \(v\) in a connected graph \(G\) is the distance between \(v\) and a vertex furthest from \(v\). The center \(C(G)\) is the subgraph induced by those vertices whose eccentricity is the radius of \(G\), denoted \(\mathrm{rad}G\), and the periphery \(P(G)\) is the subgraph induced by those vertices with eccentricity equal to the diameter of \(G\), denoted \(\mathrm{diam}G\). The annulus \(\mathrm{Ann}(G)\) is the subgraph induced by those vertices with eccentricities strictly between the radius and diameter of \(G\). In a graph \(G\) where \(\mathrm{rad}G < \mathrm{diam}G\), the interior of \(G\) is the subgraph \(\mathrm{Int}(G)\) induced by the vertices \(v\) with \(e(v) < \mathrm{diam}G\). Otherwise, if \(\mathrm{rad}G = \mathrm{diam}G\), then \(\mathrm{Int}(G) = G\). Another subgraph for a connected graph \(G\) with \(\mathrm{rad}G < \mathrm{diam}G\), called the exterior of \(G\), is defined as the subgraph \(\mathrm{Ext}(G)\) induced by the vertices \(v\) with \(\mathrm{rad}G < e(v)\). As with the interior, if \(\mathrm{rad}G = \mathrm{diam}G\), then \(\mathrm{Ext}(G) = G\). In this paper, the annulus, interior, and exterior subgraphs in trees are characterized.
This paper investigates the dihedral group as the array stabilizer of an augmented \(k\)-set of mutually orthogonal Latin squares. Necessary conditions for the stabilizer to be a dihedral group are established. A set of two-variable identities essential for a dihedral group to be contained in an array stabilizer are determined. Infinite classes of models that satisfy the identities are constructed.
A proper vertex coloring of a graph \(G = (V, E)\) is acyclic if \(G\) contains no bicolored cycle. A graph \(G\) is acyclically \(L\)-list colorable if for a given list assignment \(L = \{L(v) : v \in V\}\), there exists a proper acyclic coloring \(\phi\) of \(G\) such that \(\phi(v) \in L(v)\) for all \(v \in V(G)\). If \(G\) is acyclically \(L\)-list colorable for any list assignment with \(|L(v)| = k\) for all \(v \in V\), then \(G\) is acyclically \(k\)-choosable. In this paper, it is proved that every toroidal graph without 4- and 6-cycles is acyclically \(5\)-choosable.
The centro-polyhedral group \(\langle l,m,n\rangle\), for \(l, m, n \in \mathbb{Z}\), is defined by the presentation
\[\langle x, y, z : x^l = y^m = z^n = xyz \rangle.\]
In this paper, we obtain the periods of \(k\)-nacci sequences in centro-polyhedral groups and related groups.
We study two-path convexity in bipartite tournaments. For a bipartite tournament, we obtain both a necessary condition and a sufficient condition on the adjacency matrix for its rank to be two. We then investigate 4-cycles in bipartite tournaments of small rank. We show that every vertex in a bipartite tournament of rank two lies on a four cycle, and bipartite tournaments with a maximum number of 4-cycles do not necessarily have minimum rank.
A set \(S\) of vertices in a graph \(G\) is a clique dominating set of \(G\) if \(S\) contains at least one vertex of every clique \(C\) of \(G\). The clique domination number \(\gamma_q(G)\) and the upper clique domination number \(\gamma_q(G)\) are, respectively, the minimum and maximum cardinalities of a minimal clique dominating set of \(G\). In this paper, we prove that the problem of computing \(\Gamma_q(G)\) is NP-complete even for split graphs and the problem of computing \(\gamma_q(G)\) is NP-complete even for chordal graphs. In addition, for a block graph \(BG\) we show that the clique domination number is bounded above by the vertex independence number (\(\gamma_q(BG) \leq \beta(BG)\)) and give a linear algorithm for computing \(\gamma_q(BG)\).
Katerinis established the following result in [1]. Let \(G\) be a simple graph with \(\delta(G) \geq \lfloor\frac{|V(G)|}{2}+k\), where \(k\) is a non-negative integer. Let \(f : V(G) \to \mathbb{Z}^+\) be a function having the following properties:
(1) \(\frac{1}{2}\left({d_G(v) – (k+1)}{2}\right) \leq f(v) \leq \frac{1}{2}\left({d_G(v) + (k+1)}{2}\right)\) for every \(v \in V(G)\),
(2) \(\sum_{v\in V(G)} f(v) = |E(G)|\).
Then \(G\) has an orientation \(D\) such that \(d^+_D(v) = f(v)\), for every \(v \in V(G)\). In this paper, we focus on the sharpness of the above two inequalities.
A cosimple regular matroid \(M\) does not have disjoint circuits if and only if \(M \in \{M(K_{3,3}), M^*(K_n) \mid n \geq 3\}\). This extends a former result of Erdős and Pósa on graphs without disjoint circuits.
Suppose \(G\) is a finite graph with vertex-set \(V(G)\) and edge-set \(E(G)\). An \((a, d)\)-edge-antimagic total labeling on \(G\) is a one-to-one map \(f\) from \(V(G) \cup E(G)\) onto the integers \(1, 2, \ldots, |V(G)| + |E(G)|\) with the property that the edge-weights \(w(uv) = f(u) + f(v) + f(uv)\), \(uv \in E(G)\), form an arithmetic progression starting from \(a\) and having common difference \(d\). Such a labeling is called super if the smallest labels appear on the vertices. In this paper, we investigate the existence of super \((a, d)\)-edge-antimagic total labelings of disjoint union of multiple copies of complete bipartite graph.
Let \(G = (V, E)\) be a graph with no isolated vertex. A classical observation in domination theory is that if \(D\) is a minimum dominating set of \(G\), then \(V \setminus D\) is also a dominating set of \(G\). A set \(D’\) is an inverse dominating set of \(G\) if \(D’\) is a dominating set of \(G\) and \(D’ \subseteq V \setminus D\) for some minimum dominating set \(D\) of \(G\). The inverse domination number of \(G\) is the minimum cardinality among all inverse dominating sets of \(G\). The independence number of \(G\) is the maximum cardinality of an independent set of vertices in \(G\). Domke, Dunbar, and Markus (Ars Combin. \(72 (2004), 149-160)\) conjectured that the inverse domination number of \(G\) is at most the independence number of \(G\). We prove this conjecture for special families of graphs, including claw-free graphs, bipartite graphs, split graphs, very well covered graphs, chordal graphs, and cactus graphs.
A \(\lambda\)-design on \(v\) points is a set of \(v\) distinct subsets (blocks) of a \(v\)-set such that any two different blocks meet in exactly \(\lambda\) points and not all of the blocks have the same size. Ryser’s and Woodall’s \(\lambda\)-design conjecture states that every \(\lambda\)-design can be obtained from a symmetric design by a certain complementation procedure. A result of Ryser and Woodall establishes that there exist two integers, \(r\) and \(r^*\), such that each point in a \(\lambda\)-design is in exactly \(r\) or \(r^*\) blocks. The main result of the present paper is that the \(\lambda\)-design conjecture is true for \(\lambda\)-designs with \(\gcd(r-1,r^*-1)=7\).
Improving on Domokos’s improvement of Swan’s theorem, we show that under certain conditions on a finite digraph, whenever \(p,q\) are vertices, then the number of even Eulerian paths from \(p\) to \(q\) is the same as the number of odd ones from \(p\) to \(q\).
Double-loop networks have been widely studied as architecture for local area networks. A double-loop network \(G(N;s_1,s_2)\) is a digraph with \(N\) vertices \(0,1,\ldots,N-1\) and \(2N\) edges of two types:
\(s_1-edge\): \(i \rightarrow i+s_1 \pmod{N}\); \(i=0,1,\ldots,N-1\).
\(s_2-edge\): \(i \rightarrow i+s_2 \pmod{N}\); \(i=0,1,\ldots,N-1\).
for some fixed steps \(1 \leq s_1 < s_2 < N\) with \(\gcd(N,s_1,s_2) = 1\). Let \(D(N;s_1,s_2)\) be the diameter of \(G\) and let us define \(D(N) = \min\{D(N;s_1,s_2) | 1 \leq s_1 < s_2 < N \text{ and } gcd(N,s_1,s_2) = 1\}\), and \(D_1(N) = \min\{D(N;1,s) | 1 < s < N\}\). If \(N\) is a positive integer and \(D(N) < D_1(N)\), then \(N\) is called a non-unit step integer or a nus integer. Xu and Aguild et al. gave some infinite families of 0-tight nus integers with \(D_1(N) – D(N) \geq 1\). In this work, we give a method for finding infinite families of nus integers. As application examples, we give one infinite family of 0-tight nus integers with \(D_1(N) – D(N) \geq 5\), one infinite family of 2-tight nus integers with \(D_1(N) – D(N) \geq 1\) and one infinite family of 3-tight nus integers with \(D_1(N) – D(N) \geq 1\).
Ramanujan’s \(\mathop{_1\psi_1}\)-summation formula is one of the fundamental identities in basic hypergeometric series. We review proofs of this identity and clarify its connections with other basic hypergeometric series transformations and formulae. In particular, we shall put our main emphasis on methods that can be used not only to provide deeper insight into Ramanujan’s \(\mathop{_1\psi_1}\)-summation formula, but also to derive new transformations and identities for basic hypergeometric series.
A diagonalised lattice is a two dimensional grid, where we add exactly one arbitrary diagonal in each square, and color each vertex black or white.We show that for every diagonalised lattice there is a walk from the left to the right, using only black vertices, if and only if there is no walk from the top to the bottom, using only white vertices.
A terrace for \(\mathbb{Z}_m\) is an arrangement \((a_1, a_2, \ldots, a_m)\) of the \(m\) elements of \(\mathbb{Z}_m\) such that the sets of differences \(a_{i+1} – a_i\) and \(a_i – a_{i+1}\) (\(i = 1, 2, \ldots, m-1\)) between them contain each element of \(\mathbb{Z}_m \setminus \{0\}\) exactly twice. For \(m\) odd, many procedures are available for constructing power-sequence terraces for \(\mathbb{Z}_m\); each such terrace may be partitioned into segments one of which contains merely the zero element of \(\mathbb{Z}_m\) whereas each other segment is either (a) a sequence of successive powers of a non-zero element of \(\mathbb{Z}_m\) or (b) such a sequence multiplied throughout by a constant. For \(n\) an odd prime power satisfying \(n \equiv 1\) or \(3 \pmod{8}\), this idea has previously been extended by using power-sequences in \(\mathbb{Z}_n\) to produce some \(\mathbb{Z}_m\) terraces \((a_1, a_2, \ldots, a_m)\) where \(m = n+1 = 2^\mu\), with \(a_{i+1} – a_i = -(a_{i+1+\mu} – a_{i+\mu})\) for all \(i \in [1, \mu-1]\). Each of these “da capo directed terraces” consists of a sequence of segments, one containing just the element \(0\) and another just containing the element \(n\), the remaining segments each being of type (a) or (b) above with each of its distinct entries \(z\) from \(\mathbb{Z}_n \setminus \{0\}\) evaluated so that \(1 \leq x \leq n-1\). Now, for many odd prime powers \(n\) satisfying \(n \equiv 1 \pmod{4}\), we similarly produce narcissistic terraces for \(\mathbb{Z}_{n+1}\); these have \(a_{i+1} – a_i = a_{m-i+1} – a_{m-i}\) for all \(i \in [1, \mu-1]\).
We determine the full Sylow \(p\)-subgroup of the automorphism group of transitive \(k\)-ary relational structures of order \(p^2\), \(p\) a prime. We then find the full automorphism group of transitive ternary relational structures of order \(p^2\), for those values of \(p\) for which \({A_p}\) is the only doubly-transitive nonabelian simple group of degree \(p\). Finally, we determine optimal necessary and sufficient conditions for two Cayley \(k\)-ary relational structures of order \(p^2\), \(k < p\), to be isomorphic.
Let \(G\) be a finite group, \(S\) (possibly, contains the identity element) be a subset of \(G\). The Bi-Cayley graph \(\text{BC}(G, S)\) is a bipartite graph with vertex set \(G \times \{0,1\}\) and edge set \(\{\{(g,0), (gs,1)\}, g \in G, s \in S\}\). A graph \(X\) is said to be super-edge-connected if every minimum edge cut of \(X\) is a set of edges incident with some vertex. The restricted edge connectivity \(\lambda'(X)\) of \(X\) is the minimum number of edges whose removal disconnects \(X\) into nontrivial components. A \(k\)-regular graph \(X\) is said to be optimally super-edge-connected if \(X\) is super-edge-connected and its restricted edge connectivity attains the maximum \(2k-2\). In this paper, we show that all connected Bi-Cayley graphs, except even cycles, are optimally super-edge-connected.
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)\).
In this paper, we consider the relationships between the sums of the generalized order-\(k\) Fibonacci and Lucas numbers and \(1\)-factors of bipartite graphs.
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.
The modified Zagreb indices are important topological indices in mathematical chemistry. In this paper, we study the modified Zagreb indices of disjunctions and symmetric differences.
Given a graph \(G\) and a non-negative integer \(g\), the \(g\)-extra-connectivity of \(G\) (written \(\kappa_g(G)\)) is the minimum cardinality of a set of vertices of \(G\), if any, whose deletion disconnects \(G\), and every remaining component has more than \(g\) vertices. The usual connectivity and superconnectivity of \(G\) correspond to \(\kappa_0(G)\) and \(\kappa_1(G)\), respectively. In this paper, we determine \(\kappa_g(P_{n_1} \times P_{n_2} \times \cdots \times P_{n_s})\) for \(0 \leq g \leq s\), where \(\times\) denotes the Cartesian product of graphs. We generalize \(\kappa_g(Q_n)\) for \(0 \leq g \leq n\), \(n \geq 4\), where \(Q_n\) denotes the \(n\)-cube.
A graph labeling is an assignment of integers (labels) to the vertices and/or edges of a graph. Within vertex labelings, two main branches can be distinguished: difference vertex labelings that associate each edge of the graph with the difference of the labels of its endpoints. Graceful and edge-antimagic vertex labelings correspond to these branches, respectively. In this paper, we study some connections between them. Indeed, we study the conditions that allow us to transform any \(a\)-labeling (a special case of graceful labeling) of a tree into an \((a, 1)\)- and \((a, 2)\)-edge antimagic vertex labeling.
The domination number \(\gamma(G)\) of a graph \(G\) is the minimum cardinality among all dominating sets of \(G\), and the independence number \(\alpha(G)\) of \(G\) is the maximum cardinality among all independent sets of \(G\). For any graph \(G\), it is easy to see that \(\gamma(G) \leq \alpha(G)\). In this paper, we present a characterization of trees \(T\) with \(\gamma(T) = \alpha(T)\).
This paper generalizes the concept of locally connected graphs. A graph \(G\) is triangularly connected if for every pair of edges \(e_1, e_2 \in E(G)\), \(G\) has a sequence of \(3\)-cycles \(C_1, C_2, \ldots, C_l\) such that \(e_1 \in C_1, e_2 \in C_l\) and \(E(C_i) \cap E(C_{i+1}) \neq \emptyset\) for \(1 \leq i \leq l-1\). In this paper, we show that every triangularly connected \(K_{1,4}\)-free almost claw-free graph on at least three vertices is fully cycle extendable.
Let \(G = (V,E)\) be a simple graph. \({N}\) and \({Z}\) denote the set of all positive integers and the set of all integers, respectively. The sum graph \(G^+(S)\) of a finite subset \(S \subset{N}\) is the graph \((S, {E})\) with \(uv \in {E}\) if and only if \(u+v \in S\). \(G\) is a sum graph if it is isomorphic to the sum graph of some \(S \subseteq {N}\). The sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices, which result in a sum graph when added to \(G\). By extending \({N}\) to \({Z}\), the notions of the integral sum graph and the integral sum number of \(G\) are obtained, respectively. In this paper, we prove that \(\zeta(\overline{C_n}) = \sigma(\overline{C_n}) = 2n-7\) and that \(\zeta(\overline{W_n}) = \sigma(\overline{W_n}) = 2n-8\) for \(n \geq 7\).
We investigate the relationship between geodetic sets, \(k\)-geodetic sets, dominating sets, and independent sets in arbitrary graphs. As a consequence of the study, we provide several tight bounds on the geodetic number of a graph.
For \(1 \leq d \leq v-1\), let \(V\) denote the \(2v\)-dimensional symplectic space over a finite field \({F}_q\), and fix a \((v-d)\)-dimensional totally isotropic subspace \(W\) of \(V\). Let \({L}(d, 2v) = {P}\cup \{V\}\), where \({P} = \{A \mid A \text{ is a subspace of } V, A \cap W = \{0\} \text{ and } A \subset W^\perp\}\). Partially ordered by ordinary or reverse inclusion, two families of finite atomic lattices are obtained. This article discusses their geometricity, and computes their characteristic polynomials.
Let \(M\) be a graph, and let \(H(M)\) denote the homeomorphism class of \(M\), that is, the set of all graphs obtained from \(M\) by replacing every edge by a `chain’ of edges in series. Given \(M\) it is possible, either using the `chain polynomial’ introduced by E. G. Whitehead and myself (Discrete Math. \(204(1999) 337-356)\) or by ad hoc methods, to obtain an expression which subsumes the chromatic polynomials of all the graphs in \(H(M)\). It is a function of the number of colors and the lengths of the chains replacing the edges of \(M\). This function contains complete information about the chromatic properties of these graphs. In particular, it holds the answer to the question “Which pairs of graphs in \(H(M)\) are chromatically equivalent”. However, extracting this information is not an easy task.
In this paper, I present a method for answering this question. Although at first sight it appears to be wildly impractical, it can be persuaded to yield results for some small graphs. Specific results are given, as well as some general theorems. Among the latter is the theorem that, for any given integer \(\gamma\), almost all cyclically \(3\)-connected graphs with cyclomatic number \(\gamma\) are chromatically unique.
The analogous problem for the Tutte polynomial is also discussed, and some results are given.
Let \(G\) be a simple graph of order \(p \geq 2\). A proper \(k\)-total coloring of a simple graph \(G\) is called a \(k\)-vertex distinguishing proper total coloring (\(k\)-VDTC) if for any two distinct vertices \(u\) and \(v\) of \(G\), the set of colors assigned to \(u\) and its incident edges differs from the set of colors assigned to \(v\) and its incident edges. The notation \(\chi_{vt}(G)\) indicates the smallest number of colors required for which \(G\) admits a \(k\)-VDTC with \(k \geq \chi_{vt}(G)\). For every integer \(m \geq 3\), we will present a graph \(G\) of maximum degree \(m\) such that \(\chi_{vt}(G) < \chi_{vt}(H)\) for some proper subgraph \(H \subseteq G\).
Let \(G = (V,E)\) be a graph. Let \(\gamma(G)\) and \(\gamma_t(G)\) be the domination and total domination number of a graph \(G\), respectively. The \(\gamma\)-criticality and \(\gamma_t\)-criticality of Harary graphs are studied. The Question \(2\) of the paper [W. Goddard et al., The Diameter of total domination vertex critical graphs, Discrete Math. \(286 (2004), 255-261]\) is fully answered with the family of Harary graphs. It is answered to the second part of Question \(1\) of that paper with some Harary graphs.
Let \(G\) be a connected graph. The hyper-Wiener index \(WW(G)\) is defined as \(WW(G) = \frac{1}{2}\sum_{u,v \in V(G)} d(u,v) + \frac{1}{2} \sum_{u,v \in V(G)} d^2(u,v),\) with the summation going over all pairs of vertices in \(G\) and \(d(u,v)\) denotes the distance between \(u\) and \(v\) in \(G\). In this paper, we determine the upper or lower bounds on hyper-Wiener index of trees with given number of pendent vertices, matching number, independence number, domination number, diameter, radius, and maximum degree.
A large set of resolvable Mendelsohn triple systems of order \(v\), denoted by \(\text{LRMTS}(v)\), is a collection of \(v-2\) \(\text{RMTS}(v)\)s based on \(v\)-set \(X\), such that every Mendelsohn triple of \(X\) occurs as a block in exactly one of the \(v-2\) \(\text{RMTS}(v)\)s. In this paper, we use \(\text{TRIQ}\) and \(\text{LR-design}\) to present a new product construction for \(\text{LRMTS}(v)\)s. This provides some new infinite families of \(\text{LRMTS}(v)\)s.
In this paper, we investigate the existence of nontrivial solutions for the equation \(y(G \Box H) – \gamma(G) \gamma(H)\) fixing one factor. For the complete bipartite graphs \(K_{m,n}\), we characterize all nontrivial solutions when \(m = 2, n \geq 3\) and prove the nonexistence of solutions when \(m \geq 2, n \leq 3\). In addition, it is proved that the above equation has no nontrivial solution if \(A\) is one of the graphs obtained from \(G\), the cycle of length \(n\), either by adding a vertex and one pendant edge joining this vertex to any vertex to any \(v\in V(C_n)\), or by adding one chord joining two alternating vertices of \(C_n\).
For a graph \(G = (V(G), E(G))\), let \(i(G)\) be the number of isolated vertices in \(G\). The isolated toughness of \(G\) is defined as
\(I(G) = \min\left\{\frac{|S|}{i(G-S)}: S \subseteq V(G), i(G-S) \geq 2\right\}\) if \(G\) is not complete; \(I(G) = |V(G)|-1\) otherwise. In this paper, several sufficient conditions in terms of isolated toughness are obtained for the existence of \([a, b]\)-factors avoiding given subgraphs, e.g., a set of vertices, a set of edges and a matching, respectively.
In a graph \(G\), the distance \(d(u,v)\) between a pair of vertices \(u\) and \(v\) is the length of a shortest path joining them. The eccentricity \(e(u)\) of a vertex \(u\) is the distance to a vertex farthest from \(u\). The minimum eccentricity is called the radius of the graph and the maximum eccentricity is called the diameter of the graph. The radial graph \(R(G)\) based on \(G\) has the vertex set as in \(G\). Two vertices \(u\) and \(v\) are adjacent in \(R(G)\) if the distance between them in \(G\) is equal to the radius of \(G\). If \(G\) is disconnected, then two vertices are adjacent in \(R(G)\) if they belong to different components. The main objective of this paper is to find a necessary and sufficient condition for a graph to be a radial graph.
Let \(\{T, T’\}\) be a Latin bitrade. Then \(T\) (and \(T’\)) is said to be \((r,c,e)\)-homogeneous if each row contains precisely \(r\) entries, each column contains precisely \(c\) entries, and each entry occurs precisely \(e\) times. An \((r,c,e)\)-homogeneous Latin bitrade can be embedded on the torus only for three parameter sets, namely \((r,c,e) = (3,3,3), (4,4,2)\), or \((6,3,2)\). The first case has been completely classified by a number of authors. We present classifications for the other two cases.
In this paper, we prove an interesting property of rook polynomials for \(2\)-D square boards and extend that for rook polynomials for \(3\)-D cubic, and \(r\)-D “hypercubic” boards. In particular, we prove that for \(r\)-D rook polynomials the modulus of the sum of their roots equals their degree. We end with some further questions, mainly for the \(2\)-D and \(3\)-D case, that could serve as future projects.
Let \(G\) be a finite graph and \(H\) be a subgraph of \(G\). If \(V(H) = V(G)\), then the subgraph \(H\) is called a \({spanning \;subgraph}\) of \(G\). A spanning subgraph \(H\) of \(G\) is called an \({F-factor}\) if each component of \(H\) is isomorphic to \(F\). Further, if there exists a subgraph of \(G\) whose vertex set is \(\lambda V(G)\) and can be partitioned into \(F\)-factors, then it is called a \({\lambda-fold \;F-factor}\) of \(G\), denoted by \(S_\lambda(1,F,G)\). A \({large \; set}\) of \(\lambda\)-fold \(F\)-factors in \(G\) is a partition \(\{\mathcal{B}_i\}_{i}\) of all subgraphs of \(G\) isomorphic to \(F\), such that each \((X, \mathcal{B}_i)\) forms a \(\lambda\)-fold \(F\)-factor of \(G\). In this paper, we investigate the large set of \(\lambda\)-fold \(P_3\)-factors in \(K_{v,v}\) and obtain its existence spectrum.
Let \(k \geq 1\), \(l \geq 3\), and \(s \geq 5\) be integers. In \(1990\), Erdős and Faudree conjectured that if \(G\) is a graph of order \(4k\) with \(\delta(G) \geq 2k\), then \(G\) contains \(k\) vertex-disjoint \(4\)-cycles. In this paper, we consider an analogous question for \(5\)-cycles; that is to say, if \(G\) is a graph of order \(5k\) with \(\delta(G) \geq 3k\), then \(G\) contains \(k\) vertex-disjoint \(5\)-cycles? In support of this question, we prove that if \(G\) is a graph of order \(5k\) with \(\omega_2(G) \geq 6l – 2\), then, unless \(\overline{K_{l-2}} + K_{2l+1,2l+1} \subseteq G \subseteq K_{l-2} + K_{2l+1,2l+1}\), \(G\) contains \(l – 1\) vertex-disjoint \(5\)-cycles and a path of order \(5\), which is vertex-disjoint from the \(l – 1\) \(5\)-cycles. In fact, we prove a more general result that if \(G\) is a graph of order \(5k + 2s\) with \(\omega_2(G) \geq 6k + 2s\), then, unless \(\overline{K_{k}} + K_{2k+s,2k+s} \subseteq G \subseteq K_{k} + K_{2k+s,2k+s}\), \(G\) contains \(k+1\) vertex-disjoint \(5\)-cycles and a path of order \(2s – 5\), which is vertex-disjoint from the \(k + 1\) \(5\)-cycles. As an application of this theorem, we give a short proof for determining the exact value of \(\text{ex}(n,(k + 1)C_5)\), and characterize the extremal graph.
In this paper, we present the complex factorizations of the Jacobsthal and Jacobsthal Lucas numbers by determinants of tridiagonal matrices.
In this paper, we find families of \((0, -1, 1)\)-tridiagonal matrices whose determinants and permanents equal the negatively subscripted Fibonacci and Lucas numbers. Also, we give complex factorizations of these numbers by the first and second kinds of Chebyshev polynomials.
We classify all finite near hexagons which satisfy the following properties for a certain \(t_2 \in \{1,2,4\}\):(i) every line is incident with precisely three points;(ii) for every point \(x\), there exists a point \(y\) at distance \(3\) from \(x\);(iii) every two points at distance \(2\) from each other have either \(1\) or \(t_2 + 1\) common neighbours;(iv) every quad is big. As a corollary, we obtain a classification of all finite near hexagons satisfying (i), (ii) and (iii) with \(t_2\) equal to \(4\).
In this paper, we obtain the largest Laplacian spectral radius for bipartite graphs with given matching number and use them to characterize the extremal general graphs.
For integers \(k, \theta \leq 3\) and \(\beta \geq 1\), an integer \(k\)-set \(S\) with the smallest element \(0\) is a \((k; \beta, \theta)\)-free set if it does not contain distinct elements \(a_{i,j}\) (\(1 \leq i \leq j \leq \theta\)) such that \(\sum_{j=1}^{\theta -1}a_{i ,j} = \beta a_{i_\theta}\). The largest integer of \(S\) is denoted by \(\max(S)\). The generalized antiaverage number \(\lambda(k; \beta, \theta)\) is equal to \(\min\{\max(S) : S \text{ is a } (k^0; \delta, 0)\text{-free set}\}\). We obtain:(1) If \(\beta \notin \{\theta-2, \theta-1, \theta\}\), then \(\lambda(m; \beta, \theta) \leq (\theta-1)(m-2) + 1\); (2) If \(\beta \geq {\theta-1}\), then \(\lambda(k; \beta, \theta) \leq \min\limits_{k=m+n}\{\lambda(m;\beta,\theta)+\beta \lambda (n;\beta,\theta)+1\}\), where \(k =m+n \) with \(n>m\geq 3\) and \(\lambda(2n;\beta,\theta)\leq \lambda(n;\beta,\theta)(\beta+1)+\varepsilon\), for \(\varepsilon=1\) for \(\theta=3\) and \(\varepsilon=0\) otherwise.
A connected graph is highly irregular if the neighbors of each vertex have distinct degrees. We will show that every highly irregular tree has at most one nontrivial automorphism. The question that motivated this work concerns the proportion of highly irregular trees that are asymmetric, i.e., have no nontrivial automorphisms. A \(d\)-tree is a tree in which every vertex has degree at most \(d\). A technique for enumerating unlabeled highly irregular \(d\)-trees by automorphism group will be described for \(d \geq 4\) and results will be given for \(d = 4\). It will be shown that, for fixed \(d\), \(d \geq 4\), almost all highly irregular \(d\)-trees are asymmetric.
Combining with specific degrees or edges of a graph, this paper provides some new classes of upper embeddable graphs and extends the results in [Y. Huang, Y. Liu, Some classes of upper embeddable graphs, Acta Mathematica Scientia, \(1997, 17\)(Supp.): \(154-161\)].
A graph is called integral if all eigenvalues of its adjacency matrix are integers. In this paper, we investigate integral trees \(S(r;m_i) = S(a_1+a_2+\cdots+a_s;m_1,m_2,\ldots,m_s)\) of diameter \(4\) with \(s = 2,3\). We give a better sufficient and necessary condition for the tree \(S(a_1+a_2;m_1,m_2)\) of diameter \(4\) to be integral, from which we construct infinitely many new classes of such integral trees by solving some certain Diophantine equations. These results are different from those in the existing literature. We also construct new integral trees \(S(a_1+a_2+a_3;m_1,m_2,m_3) = S(a_1+1+1;m_1,m_2,m_3)\) of diameter \(4\) with non-square numbers \(m_2\) and \(m_3\). These results generalize some well-known results of P.Z. Yuan, D.L. Zhang \(et\) \(al\).
Zagreb indices are the best known topological indices which reflect certain structural features of organic molecules. In this paper we point out that the modified Zagreb indices are worth studying and present some results about product graphs.
Let \(g \in H(\mathcal{B})\), \(g(0) = 0\) and \(\varphi\) be a holomorphic self-map of the unit ball \(\mathbb{B}\) in \(\mathbb{C}^n\). The following integral-type operator
\[I_\varphi^g(f)(z) = \int_{0}^{1} {\mathcal{R}f(\varphi(tz))}{g(tz)}\frac{ dt}{t}, \quad f \in H(\mathbb{B}),z\in \mathbb{B},\]
was recently introduced by S. Stević and studied on some spaces of holomorphic functions on \(\mathbb{B}\), where \(\mathcal{R}f(z) = \sum_{k=1}^n z_k \frac{\partial f}{\partial z_k}(z)\) is the radial derivative of \(g\). The boundedness and compactness of this operator from generally weighted Bloch spaces to Bloch-type spaces on \(\mathbb{B}\) are investigated in this note.
We start by proving that the Henson graphs \(H_n\), \(n \geq 3\) (the homogeneous countable graphs universal for the class of all finite graphs omitting the clique of size \(n\)), are retract rigid. On the other hand, we provide a full characterization of retracts of the complement of \(H_3\). Further, we prove that each countable partial order embeds in the natural order of retractions of the complements of Henson graphs. Finally, we show that graphs omitting sufficiently large null subgraphs omit certain configurations in their endomorphism monoids.
Combining integration method with series rearrangement,we establish several closed formulae for Gauss hypergeometric series with four free parameters, which extend essentially the related results found recently by Elsner \((2005).\)
In this paper, we study the global behavior of the nonnegative equilibrium points of the difference equation
\(x_{n+1} = \frac{Ax_{n-2l}}{B+C \prod\limits_{i=0}^{2k}x_{n-i}}, n=0,1,\ldots ,\)
where \(A\), \(B\), \(C\) are nonnegative parameters, initial conditions are nonnegative real numbers, and \(k\), \(l\) are nonnegative integers, \(l \leq k\). Also, we derive solutions of some special cases of this equation.
In this paper, the critical group structure of the Cartesian product graph \(C_4 \times C_n\) is determined, where \(n \geq 3\).
Let \(G = (V, E)\) be a simple connected graph with \(7\) vertices. The degree of \(v_i \in V\) and the average of degrees of the vertices adjacent to \(v_i\) are denoted by \(d_i\) and \(m_i\), respectively. The spectral radius of \(G\) is denoted by \(\rho(G)\). In this paper, we introduce a parameter into an equation of adjacency matrix, and obtain two inequalities for upper and lower bounds of spectral radius. By assigning different values to this parameter, one can obtain some new and existing results on spectral radius. Specially, if \(G\) is a nonregular graph, then
\[\rho(G) \leq \max_{1 \leq j<i \leq n} \{ \frac{d_i m_i – d_j m_j + \sqrt{(d_i m_i – d_j m_j)^2 – 4d_i d_j(d_i-d_j) (m_i – m_j)}}{2(d_i-d_j)} \}\] and \[\rho(G)\geq \min_{1 \leq j<i \leq n} \{ \frac{d_i m_i – d_j m_j + \sqrt{(d_i m_i – d_j m_j)^2 – 4d_i d_j(d_i-d_j) (m_i – m_j)}}{2(d_i-d_j)} \}.\] If \(G\) is a bidegreed graph whose vertices of same degree have equal average of degrees, then the equality holds.
An orientation of a simple graph \(G\) is called an oriented graph. If \(D\) is an oriented graph, \(\delta(D)\) its minimum degree and \(\lambda(D)\) its edge-connectivity, then \(\lambda(D) \leq \delta(D)\). The oriented graph is called maximally edge-connected if \(\lambda(D) = \delta(D)\) and super-edge-connected, if every minimum edge-cut is trivial. In this paper, we show that an oriented graph \(D\) of order \(n\) without any clique of order \(p + 1\) in its underlying graph is maximally edge-connected when
\[n \leq 4{\lfloor\frac{p\delta(D)}{p – 1}\rfloor}-1.\]
Some related conditions for oriented graphs to be super-edge-connected are also presented.
Denote by \(\mathcal{A_n}\), the set of the polyphenyl chains with \(n\) hexagons. For any \(A_n \in \mathcal{A_n}\), let \(m_k(A_n)\) and \(i_k(A_n)\) be the numbers of \(k\)-matchings and \(k\)-independent sets of \(A_n\), respectively. In the paper, we show that for any \(A_n \in \mathcal{A_n}\) and for any \(k \geq 0\),\(m_k(M_n) \leq m_k(A_n) \leq m_k(O_n) \quad \text{and} \quad i_k(M_n) \geq i_k(A_n) \geq i_k(O_n),\) with the equalities holding if \(A_n = M_n\) or \(A_n = O_n\), where \(M_n\) and \(O_n\) are the meta-chain and the ortho-chain, respectively. These generalize some related results in \([1]\).
Let \(G = (X, Y, E(G))\) be a bipartite graph with vertex set \(V(G) = X ! Y\) and edge set \(E(G)\), and let \(g, f\) be two nonnegative integer-valued functions defined on \(V(G)\) such that \(g(x) \leq f(x)\) for each \(x \in V(G)\). A \((g, f)\)-factor of \(G\) is a spanning subgraph \(F\) of \(G\) such that \(g(x) \leq d_F(x) \leq f(x)\) for each \(x \in V(F)\); a \((g, f)\)-factorization of \(G\) is a partition of \(E(G)\) into edge-disjoint \((g, f)\)-factors. Let \(\mathcal{F} = \{F_1, F_2, \ldots, F_m\}\) be a factorization of \(G\) and \(H\) be a subgraph of \(G\) with \(m\) edges. If \(F_i\), \(1 \leq i \leq m\), has exactly \(r\) edges in common with \(H\), we say that \(F_i\) is \(r\)-orthogonal to \(H\). In this paper, it is proved that every bipartite \((0, mf-(m-1)r)\)-graph has \((0, f)\)-factorizations randomly \(r\)-orthogonal to any given subgraph with \(m\) edges if \(2r \leq f(x)\) for any \(x \in V(G)\).
We define an \(r\)-capacitated dominating set of a graph \(G = (V,E)\) as a set \(\{v_1, \ldots, v_k\} \subseteq V\) such that there is a partition \((V_1, \ldots, V_k)\) of \(V\) where for all \(i\), \( v_i \in V_i\), \(v_i\) is adjacent to all of \(V_i – \{v_i\}\), and \(|V_i| \leq r + 1\). \(\daleth_r(G)\) is the minimum cardinality of an \(r\)-capacitated dominating set. We show properties of \(\daleth_r\), especially as regards the trivial lower bound \(|V|/(r + 1)\). We calculate the value of the parameter in several graph families, and show that it is related to codes and polyominoes. The parameter is \(NP\)-complete in general to compute, but a greedy approach provides a linear-time algorithm for trees.
On the basis of joint trees introduced by Yanpei Liu, by choosing different spanning trees and classifying the associated surfaces, we obtain the explicit expressions of genus polynomials for three types of graphs, namely \(K_5^n, W_6^n\) and \(K_{3,3}^n\), which are different from the graphs whose embedding distributions by genus have been obtained. And \(K_5^n\) and \(K_{3,3}^n\) are non-planar.
We develop the necessary machinery in order to prove that hexagonal tilings are uniquely determined by their Tutte polynomial, showing as an example how to apply this technique to the toroidal hexagonal tiling.
A \((d,1)\)-totel labelling of a graph \(G\) is an assignment of integers to \(V(G) \cap E(G)\) such that: (i) any two adjacent vertices of \(G\) receive distinct integers, (ii) any two adjacent edges of \(G\) receive distinct integers, and (iii) a vertex and its incident edge receive integers that differ by at least \(d\) in absolute value. The span of a \((d,1)\)-total labelling is the maximum difference between two labels. The minimum span of labels required for such a \((d, 1)\)-total labelling of \(G\) is called the \((d, 1)\)-total number and is denoted by \(\lambda_d^T(G)\). In this paper, we prove that \(\lambda_d^T(G)\geq d+r+1 \) for \(r\)-regular nonbipartite graphs with \(d \geq r \geq 3\) and determine the \((d, 1)\)-total numbers of flower snarks and of quasi flower snarks.
Let \(G = (V,E)\) be a simple graph with the vertex set \(V\) and the edge set \(E\). \(G\) is a sum graph if there exists a labelling \(f\) of the vertices of \(G\) into distinct positive integers such that \(uv \in E\) if and only if \( f(w)=f(u) + f(v) \) for some vertex \(w \in V\). Such a labelling \(f\) is called a sum labelling of \(G\). The sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices which result in a sum graph when added to \(G\). Similarly, the integral sum graph and the integral sum number \(\zeta(G)\) are also defined. The difference is that the labels may be any distinct integers.
In this paper, we will determine that
\[\begin{cases}
0 = \zeta(\overline{P_4}) < \sigma(\overline{P_4}) = 1;\\
1 = \zeta(\overline{P_5}) < \sigma(\overline{P_5}) = 2;\\
3 = \zeta(\overline{P_6}) < \sigma(\overline{P_6}) = 4;\\
\zeta(\overline{P_n}) = \sigma(\overline{P_n}) = 0, \text{ for } n = 1, 2, 3;\\
\zeta(\overline{P_n}) = \sigma(\overline{P_n}) = 2n – 7, \text{ for } n \geq 7;
\end{cases}\]
and
\[\begin{cases}
0 = \zeta(\overline{F_5}) < \sigma(\overline{F_5}) = 1;\\
2 = \zeta(\overline{F_5}) < \sigma(\overline{F_6}) = 2;\\
\zeta(\overline{F_c}) = \sigma(\overline{F_n}) = 0, \text{ for } n =3,4;\\
\zeta(\overline{F_n}) = \sigma(\overline{F_n}) = 2n – 8, \text{ for } n \geq 7.
\end{cases}\]
The Padmakar-Ivan (PI) index is a Wiener-Szeged-like topological index which reflects certain structural features of organic molecules. In this paper, we study the PI indices of bicyclic graphs whose cycles do not share two or more common vertices.
For each of the parameter sets \((30, 7, 15)\) and \((26, 12, 55)\), a simple \(3\)-design is given. They have \(\text{PSL}(2, 29)\) and \(\text{PSL}(2, 25)\) as their automorphism group, respectively. Each of the two simple \(3\)-designs is the first one ever known with the parameter set given and \(4\) in each of the two parameter sets is minimal for the given \(v\) and \(k\).
In this paper, we study linear codes over finite chain rings. We relate linear cyclic codes, \((1 + \gamma^k)\)-cyclic codes and \((1 – \gamma^k)\)-cyclic codes over a finite chain ring \(R\), where \(\gamma\) is a fixed generator of the unique maximal ideal of the finite chain ring \(R\), and the nilpotency index of \(\gamma\) is \(k+1\). We also characterize the structure of \((1+\gamma^k)\)-cyclic codes and \((1 – \gamma^k)\)-cyclic codes over finite chain rings.
Let \(G\) be a graph with \(n\) vertices. The mean integrity of \(G\) is defined as follows:\(J(G) = min_{P \subseteq V} \{|P| + \tilde{m}(G – P)\},\) where \(\tilde{m}(G – P) = \frac{1}{n-|P|}\sum_{v \in G – P} n_v\) and \(n_v\) is the size of the component containing \(v\). The main result of this article is a formula for the mean integrity of a path \(P_n\) of \(n\) vertices. A corollary of this formula establishes the mean integrity of a cycle \(C_n\) of \(n\) vertices.
It is known that any reducible additive hereditary graph property has infinitely many minimal forbidden graphs, however the proof of this fact is not constructive. The purpose of this paper is to construct infinite families of minimal forbidden graphs for some classes of reducible properties. The well-known Hajós’ construction is generalized and some of its applications are presented.
In this paper, we prove that for any graph \(G\), there is a dominating induced subgraph which is a cograph. Two new domination parameters \(\gamma_{cd}\) – the cographic domination number and \(\gamma_{gcd}\) – the global cographic domination number are defined. Some properties, including complexity aspects, are discussed.
Given a permutation \(\pi\) chosen uniformly from \(S_n\), we explore the joint distribution of \(\pi(1)\) and the number of descents in \(\pi\). We obtain a formula for the number of permutations with \(Des(\pi) = d\) and \(\pi(1) = k\), and use it to show that if \(Des(\pi)\) is fixed at \(d\), then the expected value of \(\pi(1)\) is \(d+1\). We go on to derive generating functions for the joint distribution, show that it is unimodal if viewed correctly, and show that when \(d\) is small the distribution of \(\pi(1)\) among the permutations with \(d\) descents is approximately geometric. Applications to Stein’s method and the Neggers-Stanley problem are presented.
A graph is called induced matching extendable, if every induced matching of it is contained in a perfect matching of it. A graph \(G\) is called \(2k\)-vertex deletable induced matching extendable, if \(G — S\) is induced matching extendable for every \(S \subset V(G)\) with \(|S| = 2k\). The following results are proved in this paper. (1) If \(\kappa(G) \geq \lceil \frac{v(G)}{3} \rceil +1\) and \(\max\{d(u), d(v)\} \geq \frac{2v(G)+1}{3}\) for every two nonadjacent vertices \(u\) and \(v\), then \(G\) is induced matching extendable. (2) If \(\kappa(G) \geq \lceil \frac{v(G)+4k}{3}\rceil\) and \(\max\{d(u), d(v)\} \geq \lceil \frac{2v(G)+2k}{3} \rceil\) for every two nonadjacent vertices \(u\) and \(v\), then \(G\) is \(2k\)-vertex deletable induced matching extendable. (3) If \(d(u) + d(v) \geq 2\lceil\frac{2v(G)+2k}{3} \rceil – 1\) for every two nonadjacent vertices \(u\) and \(v\), then \(G\) is \(2k\)-vertex deletable IM-extendable. Examples are given to show the tightness of all the conditions.
Bicyclic graphs are connected graphs in which the number of edges equals the number of vertices plus one. In this paper, we determine the first three graphs among all bicyclic graphs with \(n\) vertices, ordered according to their least eigenvalues in increasing order.
The modified Zagreb indices are topological indices which reflect certain structural features of organic molecules. In this paper we study the modified Zagreb indices of joins and compositions.
In \([1]\), well-ordered Steiner triple systems were introduced and used to construct \(1\)-perfect partitions of the \(n\)-cube. However, non-trivial well-ordered Steiner triple systems were only known to exist when \(v =15\). In this short note, we present a simple construction to give a non-trivial well-ordered Steiner triple system of order \(v = 2^n – 1\) for all \(n \geq 5\) and this settles a problem in \([1]\).
Different neighbor conditions are considered in \([3,4,9]\) for a graph up-embeddable. In this paper, we consider the neighbor conditions of all the pairs of vertices with diameter \(2\) and obtain the following new result: if \(|N_G(u) \cap N_G(v)| \geq 2\) for any two vertices \(u,v \in D\) where \(D = \{(u, v) | d_G(u, v) = 2, u,v \in V(G)\}\), then \(G\) is up-embeddable.
We study the factorisations of a cyclic permutation of length \(n\) as a product of a minimal number of transpositions, calculating the number \(f(n, m)\) of factorisations in which a fixed element is moved \(m\) times. In this way, we also give a new proof-in the spirit of Clarke’s proof of Cayley’s theorem on the number of labelled trees-of the fact that there are \(n^{n-2}\) such factorisations.
We show that there are relationships between a generalized Lucas sequence and the permanent and determinant of some Hessenberg matrices.
Suppose \(G\) is a simple graph with average vertex degree greater than \(k – 2\). Erdős and Sós conjectured that \(G\) contains every tree on \(k\) vertices. Sidorenko proved \(G\) contains every tree that has a vertex \(v\) with at least \(\left\lfloor\frac{k}{2}\right\rfloor – 1\) leaf neighbors. We prove this is true if \(v\) has only \(\left\lceil\frac{k}{2}\right\rceil – 2\) leaf neighbors. We generalize Sidorenko’s result by proving that if \(G\) has minimum degree \(d\), then \(G\) contains every tree that has a vertex with at least \((k – 1) – d\) leaf neighbors. We use these results to prove that if \(G\) has average degree greater than \(k – 2\) and minimum degree at least \(k – 4\), then \(G\) contains every tree on \(k\) vertices.
A simple graph \(G\)is induced matching extendable, shortly IM-extendable, if every induced matching of \(G\) is included in a perfect matching of \(G\). The cyclic graph \(C_{2n}(1,k)\) is the graph with \(2n\) vertices \(x_0, x_1, \ldots, x_{2n-1}\), such that \(x_ix_j\) is an edge of \(C_{2n}(1,k)\) if either \(i-j \equiv \pm 1 \pmod{2n}\) or \(i-j \equiv \pm k \pmod{2n}\). We show in this paper that the only IM-extendable graphs in \(C_{2n}(1,k)\) are \(C_{2n}(1,3)\) for \(n \geq 4\); \(C_{2n}(1,n-1)\) for \(n \geq 3\); \(C_{2n}(1,n)\) for \(n \geq 2\); \(C_{2n}(1,\frac{n}{2})\) for \(n \geq 4\); \(C_{2n}(1,\frac{2n+1}{3})\) for \(n \geq 5\); \(C_{2n}(1,\frac{2n+2}{3})\) for \(n \leq 14\); \(C_{2n}(1,\frac{2n-2}{3})\) for \(n \leq 16\); \(C_{2n}(1,2)\) for \(n \leq 4\); \(C_{20}(1,8)\); \(C_{30}(1,6)\); \(C_{40}(1,8)\); \(C_{60}(1,12)\) and \(C_{80}(1,10)\).
For a vertex \(v\) in a graph \(G\), a local cut at \(v\) is a set of size \(d(v)\) consisting of the vertex \(x\) or the edge \(vx\) for each \(x \in N(v)\). A set \(U \subseteq V(G) \cup E(G)\) is a diameter-increasing set of \(G\) if the diameter of \(G – U\) is greater than the diameter of \(G\). In the present work, we first prove that every smallest generalized cutset of Johnson graph \(J(n,k)\) is a local cut except for \(J(4,2)\). Then we show that every smallest diameter-increasing set in \(J(n,k)\) is a subset of a local cut except for \(J(n,2)\) and \(J(6, 3)\).
Let \(G\) be a finite abelian group with exponent \(n\). Let \(s(G)\) denote the smallest integer \(l\) such that every sequence over \(G\) of length at least \(l\) has a zero-sum subsequence of length \(n\). For \(p\)-groups whose exponent is odd and sufficiently large (relative to Davenport’s constant of the group) we obtain an improved upper bound on \(s(G)\), which allows to determine \(s(G)\) precisely in special cases. Our results contain Kemnitz’ conjecture, which was recently proved, as a special case.
Let \(\mathcal{D}\) be a \(2\)-\((v,k,4)\) symmetric design, and \(G\) be a subgroup of the full automorphism group of \(\mathcal{D}\). In this paper, we prove that if \(G \leq {Aut}(\mathcal{D})\) is flag-transitive, point-primitive then \(G\) is of affine or almost simple type. We prove further that if a nontrivial \(2\)-\((v, k, 4)\) symmetric design has a flag-transitive, point-primitive, almost simple automorphism group \(G\), then \(\text{Soc}(G)\) is not a sporadic simple group.
We prove explicit formulas for the rank polynomial and Whitney numbers of the distributive lattice of order ideals of the garland poset, ordered by inclusion.
A semi-double graph is such a connected multi-graph that each multi-edge consists of two edges. If there is at most one loop at each vertex of a semi-double graph, then this graph is called a single-petal graph. In this paper, we obtained that if \(G\) is a connected (resp. \(2\)-edge-connected, \(3\)-edge-connected) simple graph of order \(n\), then \(G\) is upper embeddable if \(d_G(u) + d_G(v) \geq \left\lceil\frac{2n-3}{2}\right\rceil\) (resp. \(d_G(u) + d_G(v) \geq \left\lceil\frac{2n-2}{3}\right\rceil, d_G(u) + d_G(v) \geq \left\lceil\frac{2n-23}{2}\right\rceil\)) for any two adjacent vertices \(u\) and \(v\) of \(G\). In addition, by means of semi-double graph and single-petal graph, the upper embeddability of multi-graph and pseudograph are also discussed in this paper.
Let \(d(n, k)\) denote the number of derangements (permutations without fixed points) with \(k\) cycles of the set \([n] = \{1, 2, \ldots, n\}\). In this paper, a new explicit expression for \(d(n, k)\) is presented by graph theoretic method, and a concise regular binary tree representation for \(d(n, k)\) is provided.
This paper devotes to the investigation of \(3\)-designs admitting the special projective linear group \(\text{PSL}(2,q)\) as an automorphism group. When \(q \equiv 3 \pmod{4}\), we determine all the possible values of \(\lambda\) in the simple \(3\)-\((q+1, 7, \lambda)\) designs admitting \(\text{PSL}(2,q)\) as an automorphism group.
We give an optimal degree condition for a tripartite graph to have a spanning subgraph consisting of complete graphs of order \(3\). This result is used to give an upper bound of \(2\Delta\) for the strong chromatic number of \(n\) vertex graphs with \(\Delta \geq n/6\).
A partial Latin square \(P\) of order \(n\) is an \(n \times n\) array with entries from the set \(\{1, 2, \ldots, n\}\) such that each symbol is used at most once in each row and at most once in each column. If every cell of the array is filled, we call \(P\) a Latin square. A partial Latin square \(P\) of order \(n\) is said to be avoidable if there exists a Latin square \(L\) of order \(n\) such that \(P\) and \(L\) are disjoint. That is, corresponding cells of \(P\) and \(L\) contain different entries. In this note, we show that, with the trivial exception of the Latin square of order \(1\), every partial Latin square of order congruent to \(1\) modulo \(4\) is avoidable.
For positive integers \(k \leq n\), the crown \(C_{n,k}\) is the graph with vertex set \(\{a_0, a_1, \ldots, a_{n-1}, b_0, b_1, \ldots, b_{n-1}\}\) and edge set \(\{a_ib_j : 0 \leq i \leq n-1, j = i+1, i+2, \ldots, i+k \pmod{n}\}\). A caterpillar is a tree of order at least three which contains a path such that each vertex not on the path is adjacent to a vertex on the path. Being a connected bipartite graph, a caterpillar is balanced if the two parts of the bipartition of its vertices have equal size; otherwise, it is unbalanced. In this paper, we obtain the necessary and sufficient condition for balanced-caterpillar factorization of crowns. The criterion for unbalanced-caterpillar factorization of crowns is open. We also obtain the necessary and sufficient condition for directed caterpillar factorization of symmetric crowns.
This paper determines that the connectivity of the Cartesian product \(G_1 \square G_2\) of two graphs \(G_1\) and \(G_2\) is equal to \(\min\{\kappa_1v_2 + \kappa_2v_1, \delta_1 + \delta_2 \}\), where \(v_i, \kappa_i\), and \(\delta_i\) are the order, connectivity, and minimum degree of \(G_i\), respectively, for \(i = 1, 2\). Additionally, some necessary and sufficient conditions are given for \(G_1 \square G_2\) to be maximally connected and super-connected.
This paper deals with two types of graph labelings namely, super \((a, d)\)-edge antimagic total labeling and \((a, d)\)-vertex antimagic total labeling. We provide super \((a, d)\)-edge antimagic total labeling for disjoint unions of Harary graphs and disjoint unions of cycles. We also provide \((a,d)\)-vertex antimagic total labeling for disjoint unions of Harary graphs, disjoint unions of cycles, sun graphs and disjoint unions of sun graphs,
The existence question for a \(3\)-\((16,7,5)\) design is open, In this paper, we examine possible automorphisms of this design. We consider a minimum subset of basic permutations consisting of cycles of prime length \(p\) and prove that if a \(3\)-\((16,7,5)\) design exists, then it is either rigid or admits basic automorphisms with cycles of length \(2\) or \(3\).
We define a product summation of ordered partition \(f_j(n,m,r) = \sum{c_1^r c_2^r \ldots c_j^rc_{j+1} \ldots c_m}\), where the sum is over all positive integers \(c_1, c_2, \ldots, c_m\) with \(c_1 + c_2 + \cdots + c_m = n\) and \(0 \leq j \leq m\). We concentrate on \(f_m(n,m,r)\) in this paper. The main results are as follows:
(1) The generating function for \(f_m(n,m,r)\) and the explicit formula for \(f_m(n,m,2) , f_m(n,m,3)\) and \(f_m(n,m, 4)\) are obtained.
(2) The relationship between \(f_j(n,m,r)\) for \(r = 2,3\) and the Fibonacci and Lucas numbers is found.
It is shown that for \(2 \leq t \leq n-3\), a strict \(t\)-SB\((n,n-1)\) design does not exist, but for \(n \geq 3\), a non-strict \(2\)-SB\((n,n-1)\) design exists. The concept of large sets for Steiner triple systems is extended to SB designs and examples of large sets for SB designs are given.
It is shown that every well-defined solution to the second-order difference equation in the title, when \((A_n)_{n \in 0}\) is a two-periodic sequence such that \(\max\{A_0, A_1\} \geq 0\), is eventually periodic with period two. In the case \(\max\{A_0, A_1\} \leq 0\), it is shown the existence of unbounded solutions, by describing all solutions in terms of \(A_0\), \(A_1\), \(x_{-1}\), and \(x_0\).
This paper considers the folded hypercube \(FQ_n\) as an enhancement on the hypercube, and obtains some algebraic properties of \(FQ_n\). Using these properties, the authors show that for any two vertices \(x\) and \(y\) in \(FQ_n\), with distance \(d\) and any integers \(h \in \{d, n+1- d\}\) and \(l\) with \(h \leq l \leq 2^n – 1\), \(FQ_n\) contains an \(xy\)-path of length \(l\) and no \(xy\)-path of other length, provided that \(l\) and \(h\) have the same parity.
Let \(G\) be a \(2\)-tough graph on at least five vertices and let \(e_1, e_2\) be a pair of arbitrarily given edges of \(G\). Then
(a) There exists a \(2\)-factor in G containing \(e_1, e_2\).
(b) There exists a \(2\)-factor in G avoiding \(e_1, e_2\).
(c) There exists a \(2\)-factor in G containing \(e_1\) and avoiding \(e_2\).
In this paper, a sufficient condition is obtained for the global asymptotic stability of the following system of difference equations
\[x_{n+1} = \frac{x_ny_{n-1}}{x_ny_{n-1}+1} ,y_{n+1}=\frac{y_n x_{n-1}}{y_nx_{n-1} + 1} , \quad n = 0, 1, 2, \ldots,\]
where the initial values \((x_k, y_k) \in (0, \infty) (\text{for} k=-1,0)\).
Erdős and Sós conjectured in \(1962\) that if the average degree of a graph \(G\) exceeds \(k – 2\), then \(G\) contains every tree on \(k\) vertices. Results from Sauer and Spencer (and independent results from Zhou) prove the special case where \(G\) has \(k\) vertices. Results from Slater, Teo, and Yap prove the case where \(G\) has \(k + 1\) vertices. In \(1996\), Woźniak proved the case where \(G\) has \(k + 2\) vertices. We prove the conjecture for the case where \(G\) has \(k + 3\) vertices.
A semi-double graph is a connected multi-graph such that each multi-edge consists of two edges. If there is at most one loop at each vertex of a semi-double graph, then this graph is called a single-petal graph. Via the degree-sum of nonadjacent vertices, the up-embeddability of semi-double graphs and single-petal graphs are discussed in this paper. And the results obtained in this paper can be extended to determine the up-embeddability of multi-graphs and pseudographs.
The commuting graph of an arbitrary ring \(R\), denoted by \(\Gamma(R)\), is the graph whose vertices are all non-central elements of \(R\), and two distinct vertices \(a\) and \(b\) are adjacent if and only if \(ab = ba\). In this paper, we investigate the connectivity, the diameter, the maximum degree and the minimum degree of the commuting graph of the quaternion algebra \(\mathbb{Z}_n[i, j, k]\).
A set \(D\) of vertices of a graph \(G = (V, E)\) is a \(\textit{dominating set}\) if every vertex of \(V-D\) is adjacent to at least one vertex in \(D\). The \(\textit{domination number}\) \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\). A subset of \(V-D\), which is also a dominating set of \(G\), is called an \(\textit{averse dominating set}\) of \(G\) with respect to \(D\). The \(\textit{inverse domination number}\) \(\gamma'(G)\) equals the minimum cardinality of an inverse dominating set \(D\). In this paper, we study classes of graphs whose domination and inverse domination numbers are equal.
A strongly connected digraph \(\Gamma\) is said to be walk regular if for any nonnegative integer \(l\) and any vertex \(u\) of \(\Gamma\), the number of circuits of length \(l\) containing \(u\) depends only on \(l\). This family of digraphs is a directed version of walk regular graphs. In this paper, we discuss some basic properties of walk regular digraphs.
For any \(n \geq 2\) we let \(S_n\) be the set of permutations of the set \(\{1,2,\ldots,n\}\). A reduction \(\overline{f}\) on \(S_n\) is a set of functions \(\{f_i : 1 \leq i \leq n\}\) such that \(f_n\) is the identity function on \(\{1,2,\ldots,n-1\}\) and for \(i n_0\), such that \(\phi(n) \leq n\) for all \(n \geq n_0\), and for which \(p \downarrow \phi(n) \downarrow i = p \downarrow i \downarrow n-1\) for all \(n > n_0\), for all \(i \leq n-1\) and for all \(p \in S_n\). And the system is said to be amenable if for every \(n > n_0\) there is an integer \(k < n\) such that, for all \(p \in S_n\), \(p \downarrow k \downarrow n-1 = p \downarrow n-1\). The purpose of this paper is to study faithful reductions and linked reduction systems. We characterize amenable, linked reduction systems by means of two types of liftings by which a reduction on \(S_{n+1}\) can be formed from one on \(S_n\). And we obtain conditions for a reduction system to be faithful. One interesting consequence is that any amenable, linked reduction system which begins with a simple reduction is faithful.
Let \(N\) be a positive integer and let \(\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_l)\) be a partition of \(N\) of length \(l\), i.e., \(\sum_{i=1}^{l}\lambda_i = N\) with parts \(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_l \geq 1\). Define \(T(\lambda)\) as the partition of \(N\) with parts \(l\), \(\lambda_1 – 1, \lambda_2 – 1, \ldots, \lambda_l – 1\), ignoring any zeros that might occur. Starting with a partition \(\lambda\) of \(N\), we describe Bulgarian Solitaire by repeatedly applying the shift operation \(T\) to obtain the sequence of partitions
\[\lambda, T(\lambda), T^2(\lambda), \ldots\]
We say a partition \(\mathcal{A}\) of \(N\) is \(T\)-cyclic if \(T^i(\mu) = \mu\) for some \(i \geq 1\). Brandt \([2]\) characterized all \(T\)-cyclic partitions for Bulgarian Solitaire. In this paper, we give an inductive proof of Brandt’s result.
Let \(D\) be an acyclic digraph. The competition graph of \(D\) is a graph which has the same vertex set as \(D\) and has an edge between \(x\) and \(y\) if and only if there exists a vertex \(v\) in \(D\) such that \((x, v)\) and \((y, v)\) are arcs of \(D\). For any graph \(G\), \(G\) together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number \(k(G)\) of \(G\) is the smallest number of such isolated vertices.
A hole of a graph is a cycle of length at least \(4\) as an induced subgraph. In \(2005\), Kim \([5]\) conjectured that the competition number of a graph with \(h\) holes is at most \(h + 1\). Though Li and Chang \([8]\) and Kim et al. \([7]\) showed that her conjecture is true when the holes do not overlap much, it still remains open for the case where the holes share edges in an arbitrary way. In order to share an edge, a graph must have at least two holes and so it is natural to start with a graph with exactly two holes. In this paper, the conjecture is proved true for such a graph.
Let \(G\) be a graph with domination number \(\gamma(G)\). A dominating set \(S \subseteq V(G)\) has property \(\mathcal{UK}\) if all components of the subgraph it induces in \(G\) are complete. The union of complete graphs domination number of a graph \(G\), denoted \(\gamma_{uk}(G)\), is the minimum possible size of a dominating set of \(G\), which has property \(\mathcal{UK}\). Results on changing and unchanging of \(\gamma_{uk}(G)\) after vertex removal are presented. Also forbidden subgraph conditions sufficient to imply \(\gamma(G) = \gamma_{uk}(G)\) are given.
In this paper, we use the finite Heine \({}_{2}\Phi_1\) transformations given in \([4]\) and some elementary simplifications to obtain several Rogers-Ramanujan type identities.
Using lines in a two-dimensional vector space \({GF}(q^2)\) over \({GF}(q)\), we construct some classes of external difference families over \({GF}(q^2)\).
A digraph \(D\) is a local out-tournament if the outset of every vertex is a tournament. Here, we use local out-tournaments, whose strong components are upset tournaments, to explore the corresponding ranks of the adjacency matrices. Of specific interest is the out-tournament whose adjacency matrix has boolean, nonnegative integer, term, and real rank all equal to the number of vertices, \(n\). Corresponding results for biclique covers and partitions of the digraph are provided.
The current paper deals with two special matrices \(T_n\) and \(W_n\) related to the Pascal, Vandermonde, and Stirling matrices. As a result, various properties of the entries of \(T_n\) and \(W_n\) are obtained, including the generating functions, recurrence relations, and explicit expressions. Some additional results are also presented.
There are some results and many conjectures with the conclusion that a graph \(G\) contains all trees of given size \(k\). We prove some new results of this type.
In \([3]\), we gave a factorization of the generalized Lah matrix.In this short note, we show its another factorization. From this factorization, several interesting combinatorial identities involving the Fibonacci numbers are obtained.
Let \(\lambda K_v\) be the complete multigraph with \(v\) vertices. Let \(G\) be a finite simple graph. A \(G\)-decomposition of \(K_v\), denoted by \(G-GD_\lambda(v)\), is a pair \((X, \mathcal{B})\) where \(X\) is the vertex set of \(K_v\) and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in exactly one block of \(\mathcal{B}\). In this paper, nine graphs \(G_i\) with six vertices and nine edges are discussed, and the existence of \(G_i-GD_\lambda(v)\) is given, \(1 \leq i \leq 9\).
Let \(G = (V, E)\) be a graph. A set \(S \subseteq V\) is a restrained dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V – S\). The restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the smallest cardinality of a restrained dominating set of \(G\). It is known that if \(T\) is a tree of order \(n\), then \(\gamma_r(T) \geq \left\lceil \frac{n+2}{3} \right\rceil\). In this note, we provide a simple constructive characterization of the extremal trees \(T\) of order \(n\) achieving this lower bound.
Given non-negative integers \(r, s\), and \(t\), an \([r, s, t]\)-coloring of a graph \(G = (V(G), E(G))\) is a mapping \(c\) from \(V(G) \cup E(G)\) to the color set \(\{0, 1, \ldots, k-1\}\) such that \(|c(v_i) – c(v_j)| \geq r\) for every two adjacent vertices \(v_i, v_j\), \(|c(e_i) – c(e_j)| \geq s\) for every two adjacent edges \(e_i, e_j\), and \(|c(v_i) – c(e_i)| \geq t\) for all pairs of incident vertices and edges, respectively. The \([r, s, t]\)-chromatic number \(\chi_{r,s,t}(G)\) of \(G\) is defined to be the minimum \(k\) such that \(G\) admits an \([r, s, t]\)-coloring. We prove that \(\chi_{1,1,2}(K_5) = 7\) and \(\chi_{1,1,2}(K_6) = 8\).
We determine a recursive formula for the number of rooted complete \(N\)-ary trees with \(n\) leaves, which generalizes the formula for the sequence of Wedderburn-Etherington numbers. The diagonal sequence of our new sequences equals the sequence of numbers of rooted trees with \(N + 1\) vertices.
In this paper, we determine the conics characterizing the generalized Fibonacci and Lucas sequences with indices in arithmetic progressions, generalizing work of Melham and McDaniel.
A graph \(G = (V, E)\) is a mod sum graph if there exists a positive integer \(z\) and a labeling, \(\lambda\), of the vertices of \(G\) with distinct elements from \(\{1, 2, \ldots, z-1\}\) such that \(uv \in E\) if and only if the sum, modulo \(z\), of the labels assigned to \(u\) and \(v\) is the label of a vertex of \(G\). The mod sum number \(\rho(G)\) of a connected graph \(G\) is the smallest nonnegative integer \(m\) such that \(G \cup mK_1\), the union of \(G\) and \(m\) isolated vertices, is a mod sum graph. In Section \(2\), we prove that \(F_n\) is not a mod sum graph and give the mod sum number of \(F_n\) (\(n \geq 6\) is even). In Section \(3\), we give the mod sum number of the symmetric complete graph.
In this paper, we consider the effect of edge contraction on the domination number and total domination number of a graph. We define the (total) domination contraction number of a graph as the minimum number of edges that must be contracted in order to decrease the (total) domination number. We show that both of these two numbers are at most three for any graph. In view of this result, we classify graphs by their (total) domination contraction numbers and characterize these classes of graphs.
In this paper, connected graphs with the largest Laplacian eigenvalue at most \(\frac{5+\sqrt{13}}{2}\) are characterized. Moreover, we prove that these graphs are determined by their Laplacian spectrum.
An extended directed triple system of order \(v\) with an idempotent element (EDTS(\(v, a\))) is a collection of triples of the type \([x, y, z]\), \([x, y, x]\) or \((x, x, x)\) chosen from a \(v\)-set, such that every ordered pair (not necessarily distinct) belongs to only one triple and there are \(a\) triples of the type \((x, x, x)\). If such a design with parameters \(v\) and \(a\) exists, then it will have \(b_{v,a}\) blocks, where \(b_{v,a} = (v^2 + 2a)/3\). A necessary and sufficient condition for the existence of EDTS(\(v, 0\)) and EDTS(\(v, 1\)) are \(v \equiv 0 \pmod{3}\) and \(v \not\equiv 0 \pmod{3}\), respectively. In this paper, we have constructed two EDTS(\(v, a\))’s such that the number of common triples is in the set \(\{0, 1, 2, \ldots, b_{v,a} – 2, b_{v,a}\}\), for \(a = 0, 1\).
As applications of the Anzahl theorems in finite orthogonal spaces, we study the critical problem of totally isotropic subspaces, and obtain the critical exponent.
Let \(P(G,\lambda)\) be the chromatic polynomial of a graph \(G\). A graph \(G\) is chromatically unique if for any graph \(H\), \(P(H,\lambda) = P(G, \lambda)\) implies H is isomorphic to \(G\). In this paper, we study the chromaticity of Turén graphs with deleted edges that induce a matching or a star. As a by-product, we obtain new families of chromatically unique graphs.
Let \(\{w_n\}\) be a second-order recurrent sequence. Several identities about the sums of products of second-order recurrent sequences were obtained and the relationship between the second-order recurrent sequences and the recurrence coefficient revealed. Some identities about Lucas sequences, Lucas numbers, and Fibonacci numbers were also obtained.
In this paper, we prove that for any positive integers \(k,n\) with \(k \geq 2\) , the graph \(P_k^n\) is a divisor graph if and only if \(n \leq 2k + 2\) , where \(P^k_n\) is the \(k\) th power of the path \(P_n\). For powers of cycles we show that \(C^k_n\) is a divisor graph when \(n \leq 2k + 2\), but is not a divisor graph when \(n \geq 2k + 2\),but is not a divisor graph when \(n\geq 2k+\lfloor \frac{k}{2}\rceil,\) where \(C^k_n\) is the \(k\)th power of the cycle \(C_n\). Moreover, for odd \(n\) with \(2k+2 < n < 2k + \lfloor\frac{k}{2}\rfloor + 3\), we show that the graph \(C^k_n\) is not a divisor graph.
The Wiener index of a graph \(G\) is defined as \(W(G) = \sum_{u,v \in V(G)} d_G(u,v),\) where \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G\) and the sum goes over all pairs of vertices. In this paper, we investigate the Wiener index of unicyclic graphs with given girth and characterize the extremal graphs with the minimal and maximal Wiener index.
In this paper, we consider a random mapping, \(\hat{T}_n\), of the finite set \(\{1,2,\ldots,n\}\) into itself for which the digraph representation \(\hat{G}_n\) is constructed by:\((1)\) selecting a random number, \(\hat{L}_n\), of cyclic vertices,\((2)\) constructing a uniform random forest of size \(n\) with the selected cyclic vertices as roots, and \((3)\) forming `cycles’ of trees by applying a random permutation to the selected cyclic vertices.We investigate \(\hat{k}_n\), the size of a `typical’ component of \(\hat{G}_n\), and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of \(k\), conditioned on \(\hat{L}_n = m(n)\). As an application of our results, we show in Section \(3\) that provided \(\hat{L}_n\) is of order much larger than \(\sqrt{n}\), then the joint distribution of the normalized order statistics of the component sizes of \(\hat{G}_n\) converges to the Poisson-Dirichlet \((1)\) distribution as \(n \to \infty\). Other applications and generalizations are also discussed in Section \(3\).
De Bruijn digraphs and shuffle-exchange graphs are useful models for interconnection networks. They can be represented as group action graphs of the wrapped butterfly graph and the cube-connected cycles, respectively. The Kautz digraph has similar definitions and properties to de Bruijn digraphs. It is \(d\)-regular and strongly \(d\)-connected, thus it is a group action graph. In this paper, we use another representation of the Kautz digraph and settle the open problem posed by M.-C. Heydemann in \([6]\).
We discuss the use of \(K\)-terminal networks to represent arbitrary clutters. A given clutter has many different representations, and there does not seem to be any set of simple transformations that can be used to transform one representation of a clutter into any other. We observe that for \(t \geq 2\) the class of clutters that can be represented using no more than \(t\) terminals is closed under minors, and has infinitely many forbidden minors.
Brenti (J. Combin. Theory Ser. A \(91 (2000))\) considered a \(q\)-analogue of the Eulerian polynomials by enumerating permutations in the symmetric group \(S_n\) with respect to the numbers of excedances and cycles. Here we establish a connection between these \(q\)-Eulerian polynomials and some infinite generating functions.
Let \(K_k, C_k, T_k\), and \(P_k\) denote a complete graph on \(k\) vertices, a cycle on \(k\) vertices, a tree on \(k+1\) vertices, and a path on \(k+1\) vertices, respectively. Let \(K_m-H\) be the graph obtained from \(K_m\) by removing the edges set \(E(H)\) of the graph \(H\) (\(H\) is a subgraph of \(K_m\)). A sequence \(S\) is potentially \(K_m-H\)-graphical if it has a realization containing a \(K_m-H\) as a subgraph. Let \(\sigma(K_m-H,n)\) denote the smallest degree sum such that every \(n\)-term graphical sequence \(S\) with \(\sigma(S) \geq \sigma(K_m-H,n)\) is potentially \(K_m-H\)-graphical. In this paper, we determine the values of \(\sigma(K_{r+1}-H,n)\) for \(n \geq 4r+10, r \geq 3, r+1 \geq k \geq 4\) where \(H\) is a graph on \(k\) vertices which contains a tree on \(4\) vertices but not contains a cycle on \(3\) vertices. We also determine the values of \(\sigma(K_{r+1}-P_{2},n)\) for \(n \geq 4r+8, r \geq 3\).
In this paper, the class of \((m,n)\)-ary hypermodules is introduced and several properties and examples are found. \((m,n)\)-ary hypermodules are a generalization of hypermodules. On the other hand, we can consider \((m,n)\)-ary hypermodules as a good generalization of \((m,n)\)-ary modules. We define the fundamental relation \(\epsilon^*\) on the \((m,n)\)-ary hypermodules \(M\) as the smallest equivalence relation such that \(M/\epsilon^*\) is an \((m,n)\)-ary module, and then some related properties are investigated.
For given graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1, G_2)\) is defined to be the least positive integer \(n\) such that every graph \(G\) on \(n\) vertices, either \(G\) contains a copy of \(G_1\) or the complement of \(G\) contains a copy of \(G_2\). In this note, we show that \(R(C_m, B_n) = 2m-1\) for \(m \geq 2n-1 \geq 7\). With the help of computers, we obtain the exact values of \(14\) small cycle-book Ramsey numbers.
For positive integers \(c \geq 0\) and \(k \geq 1\), let \(n = R(c, k)\) be the least integer, provided it exists, such that every \(2\)-coloring of the set \([1,n] = \{1,\ldots,n\}\) admits a monochromatic solution to the equation \(x + y+c = 4z\) with \(x, y, z \in [1,n]\). In this paper, the precise value of \(R(c, 4)\) is shown to be \(\left\lceil{3c + 2}/{8}\right\rceil\) for all even \(c \geq 34\).
Given a positive integer \(n\) such that \(-1\) is a quadratic residue mod \(n\), we give an algorithm that computes the integers \(u\) and \(v\) which satisfy the equation \(n = u^2 + v^2\). To do this, we use the group structure of the Modular group \(\Gamma= \text{PSL}(2,\mathbb{Z})\).
For a graph \(G = (V(G),E(G))\), a set \(S \subseteq V(G)\) is called a dominating set if \(N_G[S] = V(G)\). A dominating set \(S\) is said to be minimal if no proper subset \(S’ \subset S\) is a dominating set. Let \(\gamma(G)\) (called the domination number) and \(\Gamma(G)\) (called the upper domination number) be the minimum cardinality and the maximum cardinality of a minimal dominating set of \(G\), respectively. For a tree \(T\) of order \(n \geq 2\), it is obvious that \(1 = \gamma(K_{1,n-1}) \leq \gamma(T) \leq \Gamma(T) \leq \Gamma(K_{1,n-1}) = n-1\). Let \(t(n) = \min_{|T|=n}(\Gamma(T)-\gamma(T))\). In this paper, we determine \(t(n)\) for all natural numbers \(n\). We also characterize trees \(T\) with \(\Gamma(T) – \gamma(T) = t(n)\).
The signless \(r\)-associated Stirling numbers of the first kind \(d_r(n, k)\) counts the number of permutations of the set \(\{1,2,\ldots,n\}\) that have exactly \(k\) cycles, each of which is of length greater than or equal to \(r\), where \(r\)is a fixed positive integer. F. Brenti obtained that the generating polynomials of the numbers \(d_r(n, k)\) have only real zeros. Here we consider the location of zeros of these polynomials.
A kite-design of order \(n\) is a decomposition of the complete graph \(K_n\) into kites. Such systems exist precisely when \(n \equiv 0,1 \pmod{8}\). Two kite systems \((X,\mathcal{K}_1)\) and \((X,\mathcal{K}_2)\) are said to intersect in \(m\) pairwise disjoint blocks if \(|\mathcal{K}_1 \cap \mathcal{K}_2| = m\) and all blocks in \(\mathcal{K}_1 \cap \mathcal{K}_2\) are pairwise disjoint. In this paper, we determine all the possible values of \(m\) such that there are two kite-designs of order \(n\) intersecting in \(m\) pairwise disjoint blocks, for all \(n \equiv 0,1 \pmod{8}\).
In this note, we present some upper bounds for the \(k\)th largest eigenvalue of the adjacency matrix as well as the Laplacian matrix of graphs. Special attention is paid to the Laplacian matrix of trees.
Let \(P(G, \lambda)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent, written \(G \sim H\), if \(P(G, \lambda) = P(H, \lambda)\). A graph \(G\) is chromatically unique, written \(x\)-unique, if for any graph \(H\), \(G \sim H\) implies that \(G\) is isomorphic with \(H\). In this paper, we prove that the graph \(\theta(a_1, a_2, \ldots, a_6)\) is \(x\)-unique for exactly two distinct values of \(a_1, a_2, \ldots, a_6\).
In this paper, we give an explicit expression of the genus distributions of \(M_j^n\), for \(j = 1, 2, \ldots, 11\), which are introduced in the previous paper “Orientable embedding distributions by genus for certain types of non-planar graphs”. For a connected graph \(G = (V, E)\) with a cycle, let \(e\) be an edge on a cycle. By adding \(2n\) vertices \(u_1, u_2,u_3 \ldots, u_n, v_1, v_2,v_3 \ldots, v_n\) on \(e\) in sequence and connecting \(u_k, v_k\) for \(1 \leq k \leq n\), a non-planar graph \(G_n\) is obtained for \(n \geq 3\). Thus, the orientable embedding distribution of \(G_n\) by genus is obtained via the genus distributions of \(M_j^n\).
A graph \(G\) is \(N^m\)-locally connected if for every vertex \(v\) in \(G\), the vertices not equal to \(v\) and with distance at most \(m\) to \(v\) induce a connected subgraph in \(G\). In this note, we first present a counterexample to the conjecture that every \(3\)-connected, \(N^2\)-locally connected claw-free graph is hamiltonian and then show that both connected \(N^2\)-locally connected claw-free graph and connected \(N^3\)-locally connected claw-free graph with minimum degree at least three have connected even \([2, 4]\)-factors.
In J.-P. Serre’s \(Lettre \;à\; M. Tsfasman\) \([3]\), an interesting bound for the maximal number of points on a hypersurface of the \(n\)-dimensional projective space \(PG(n,q)\) over the Galois field \(GF(q)\) with \(q\) elements is given. Using essentially the same combinatorial technique as in \([3]\), we provide a bound which is relative to the maximal dimension of a subspace of \(PG(n,q)\) which is completely contained in the hypersurface. The lower that dimension, the better the bound. Next, by using a different argument, we derive a bound which is again relative to the maximal dimension of a subspace of \(PG(n, q)\) which is completely contained in the hypersurface, If that dimension increases for the latter case, the bound gets better.
As such, the bounds are complementary.
In this paper, it is shown that a variation of banana trees is odd graceful, and it is also proved that the variation of banana is graceful and \(\hat{p}\)-labeling in some cases.
In this paper, we consider the generalized Fibonacci and Pell Sequences and then show the relationships between the generalized Fibonacci and Pell sequences, and the Hessenberg permanents and determinants.
In this paper, a sequence representation of Dyck paths is presented, which yields a sequence representation of the Dyck path poset \({D}\) ordered by pattern containment. This representation makes it clear that the Dyck path poset \({D}\) takes the composition poset investigated by Sagan and Vatter as a subposet, and that the pattern containment order on Dyck paths exactly agrees with a generalized subword order also presented by Sagan and Vatter. As applications of the representation, we describe the Möbius function of \({D}\) and establish the Möbius inverse of the rank function of \({D}\) in terms of Dyck sequences. In the end, a Sperner and unimodal subposet of \({D}\) is given.
A graph is said to be determined by its adjacency spectrum (or to be a DS graph, for short) if there is no other non-isomorphic graph with the same adjacency spectrum. Although all connected graphs of index less than \(2\) are known to be determined by their adjacency spectra, the classification of DS graphs of index less than \(2\) is not complete yet. The purpose of this paper is to characterize all DS graphs of index less than \(2\) with no \(Z_n\) as a component.
Let \(B\) be a bipartite graph. We obtain two new results as follows:(1) Suppose that \(u \in V(B)\) is a vertex such that \(N_B(u)\) contains at least \(|N_B(u)| – 1\) odd vertices. Let \(f : V(B) \to \mathbb{N}\) be the function such that \(f(u) = 1\) and \(f(v) = \lceil d_B(v)/2 \rceil + 1\) for \(v \in V(B) \setminus u\). Then \(B\) is \(f\)-choosable.(2) Suppose that \(u \in V(B)\) is a vertex such that every vertex in \(N_B(u)\) is odd, and \(v \in V(B)\) is an odd vertex that is not adjacent to \(u\). Let \(f : V(B) \to \mathbb{N}\) be the function such that \(f(u) = 1\), \(f(v) = \lceil d_B(v)/2 \rceil\), and \(f(w) = \lceil d_B(w)/2 \rceil + 1\) for \(w \in V(B) \setminus \{u, v\}\). Then \(B\) is \(f\)-choosable.
Assume that \(G = (V, E)\) is an undirected and connected graph, and consider \(C \subseteq V\). For every \(v \in V\), let \(I_r(v) = \{u \in C: d(u,v) \leq r\}\), where \(d(u,v)\) denotes the number of edges on any shortest path between \(u\) to \(v\) in \(G\). If all the sets \(I_r(v)\) for \(v \in V\) are pairwise different, and none of them is the empty set, \(C\) is called an \(r\)-identifying code. In this paper, we consider \(t\)-vertex-robust \(r\)-identifying codes of level \(s\), that is, \(r\)-identifying codes such that they cover every vertex at least \(s\) times and the code is vertex-robust in the sense that \(|I_r(u) \Delta I_r(v)| \geq 2t+1\) for any two different vertices \(u\) and \(v\). Vertex-robust identifying codes of different levels are examined, in particular, of level \(3\). We give bounds (sometimes exact values) on the density or cardinality of the codes in binary hypercubes and in some infinite grids.
A clique \(C\) is an extreme clique of an interval graph \(G\) if there exists some interval model of \(G\) in which \(C\) is the first clique. A graph \(G\) is homogeneously clique-representable if all cliques of \(G\) are extreme cliques. In this paper, we present characterizations of extreme cliques and homogeneously clique-representable graphs.
In this note, we show that there is no \((945, 177, 33)\)-difference set in any group \(G\) of order \(945\) with a normal subgroup \(K\) such that \(G/K \cong \mathbb{C}_{27} \times \mathbb{C}_5\), and hence no cyclic difference set with such parameters exists. This fills one entry of Baumert and Gordon’s table with “No”.
The study of patterns in permutations is a very active area of current research. Klazar defined and studied an analogous notion of pattern for set partitions. We continue this work, finding exact formulas for the number of set partitions which avoid certain specific patterns. In particular, we enumerate and characterize those partitions avoiding any partition of a 3-element set. This allows us to conclude that the corresponding sequences are P-recursive. Finally, we define a second notion of pattern in a set partition, based on its restricted growth function. Related results are obtained for this new definition.
Let \(G = (V(G), E(G))\) be a graph with \(\delta(G) \geq 1\). A set \(D \subseteq V(G)\) is a paired-dominating set if \(D\) is a dominating set and the induced subgraph \(G[D]\) contains a perfect matching. The paired domination number of \(G\), denoted by \(\gamma_p(G)\), is the minimum cardinality of a paired-dominating set of \(G\). The paired bondage number, denoted by \(b_p(G)\), is the minimum cardinality among all sets of edges \(E’ \subseteq E\) such that \(\delta(G – E’) \geq 1\) and \(\gamma_p(G – E’) > \gamma_p(G)\). For any \(b_p(G)\) edges \(E’ \subseteq E\) with \(\delta(G – E’) \geq 1\), if \(\gamma_p(G – E’) > \gamma_p(G)\), then \(G\) is called uniformly pair-bonded graph. In this paper, we prove that there exists uniformly pair-bonded tree \(T\) with \(b_p(T) = k\) for any positive integer \(k\). Furthermore, we give a constructive characterization of uniformly pair-bonded trees.
A new construction of a B-T unital using Hermitian curves and certain hypersurfaces of \(\text{PG}(3,q^2)\) is presented. Some properties of an algebraic curve containing all points of a B-T unital are also examined.
A construction of optimal quaternary codes from symmetrical Balanced Incomplete Block (BIB) design \((4t – 1, 2t – 1, t – 1)\) is described.
For integers \(s,t \geq 1\), the Ramsey number \(R(s, t)\) is defined to be the least positive integer \(n\) such that every graph on \(n\) vertices contains either a clique of order \(s\) or an independent set of order \(t\). In this note, we derive new lower bounds for the Ramsey numbers: \(R(6,8) \geq 129\), \(R(7,9) \geq 235\) and \(R(8,17) \geq 937\). The new bounds are obtained with a constructive method proposed by Xu and Xie et al. and the help of computer algorithm.
We pursue the problem of counting the imbeddings of a graph in each of the orientable surfaces. We demonstrate how to achieve this for an iterated amalgamation of arbitrarily many copies of any graph whose genus distribution is known and further analyzed into a partitioned genus distribution. We introduce the concept of recombinant strands of face-boundary walks, and we develop the use of multiple production rules for deriving simultaneous recurrences. These two ideas are central to a broad-based approach to calculating genus distributions for graphs synthesized from smaller graphs.
The super (resp., edge-) connectivity of a connected graph is the minimum cardinality of a vertex-cut (resp., an edge-cut) whose removal does not isolate a vertex. In this paper, we consider the two parameters for a special class of graphs \(G(G_p,G_1; M)\), proposed by Chen et al [Applied Math. and Computation, \(140 (2003), 245-254]\), obtained from two \(k\)-regular \(k\)-connected graphs \(G_p\) and \(G_1\), with the same order by adding a perfect matching between their vertices. Our results improve ones of Chen et al. As applications, the super connectivity and the super edge-connectivity of the \(n\)-dimensional hypercube, twisted cube, cross cube, Möbius cube and locally twisted cube are all \(2n – 2\).
We investigate the existence of \(3\)-designs and uniform large sets of \(3\)-designs with block size \(6\) admitting \(\text{PSL}(2, 2^n)\) as an automorphism group.
In \([5]\), a product summation of ordered partition \(f(n,m,r) = \sum{c_1^r + c_2^r + \cdots + c_m^r }\) was defined, where for two given positive integers \(m,r\), the sum is over all positive integers \(c_1, c_2, \ldots, c_m\) with \(c_1 + c_2 + \cdots + c_m = n\). \(f(n,r) = \sum_{i=1}^n f(n,m,r)\) was also defined. Many results on \(f(n,m,r)\) were found. However, few things have been known about \(f(n,r)\). In this paper, we give more details for \(f(n,r)\), including its two recurrences, its explicit formula via an entry of a matrix and its generating function. Unexpectedly, we obtain some interesting combinatorial identities, too.
In this paper, we obtain new general results containing sums of binomial and multinomial with coefficients satisfying a general third order linear recursive relations with indices in arithmetic progression.
The closed neighborhood \(N[e]\) of an edge \(e\) in a graph \(G\) is the set consisting of \(e\) and of all edges having a common end-vertex with \(e\). Let \(f\) be a function on \(E(G)\), the edge set of \(G\), into the set \(\{-1,1\}\). If \(\sum_{e \in N[e]} f(x) \geq 1\) for each \(e \in E(G)\), then \(f\) is called a signed edge dominating function of \(G\). The minimum of the values \(\sum_{e \in E(G)} f(e)\), taken over all signed edge dominating functions \(f\) of \(G\), is called the signed edge domination number of \(G\) and is denoted by \(\gamma’_s(G)\). It has been conjectured that \(\gamma’_s(T) \geq 1\) for every tree \(T\). In this paper we prove that this conjecture is true and then classify all trees \(T\) with \(\gamma’_s(T) = 1,2\) and \(3\).
This article is a contribution to the study of block-transitive automorphism groups of \(2\)-\((v,k,1)\) block designs. Let \(\mathcal{D}\) be a \(2\)-\((v,k,1)\) design admitting a block-transitive, point-primitive but not flag-transitive group \(G\) of automorphisms. Let \(k_1 = (k, v-1)\) and \(q = p^f\) for prime \(p\). In this paper we prove that if \(G\) and \(D\) are as above and \(q > {(2(k_rk-k_r+1)f)^{\frac{1}{4}}}\) then \(G\) does not admit a Chevalley group \(E_7(q)\) as its socle.
A graph \(G\) is called super edge-magic if there exists a bijection \(f\) from \(V(G) \cup E(G)\) to \(\{1, 2, \ldots, |V(G)| + |E(G)|\}\) such that \(f(u) + f(v) + f(uv) = C\) is a constant for any \(uv \in E(G)\) and \(f(V(G)) = \{1, 2, \ldots, |V(G)|\}\), \(f(E(G)) = \{|V(G)| + 1, |V(G)| + 2, \ldots, |V(G)| + |E(G)|\}\). R. M. Figueroa-Centeno et al. provided the following conjecture: For every integer \(n \geq 5\), the book \(B_n\) is super edge-magic if and only if \(n\) is even or \(n \equiv 5 \pmod 8\). In this paper, we show that \(B_n\) is super edge-magic for even \(n \geq 6\).
It was conjectured in \([10]\) that the upper bound for the strong chromatic index \(s'(G)\) of bipartite graphs is \(\Delta(G)^2+1\), where \(\Delta(G)\) is the largest degree of vertices in \(G\). In this note we study the strong edge coloring of some classes of bipartite graphs that belong to the class of partial cubes. We introduce the concept of \(\Theta\)-graph \(\Theta(G)\) of a partial cube \(G\), and show that \(s'(G) \leq \chi(\Theta(G))\) for every tree-like partial cube \(G\). As an application of this bound we derive that \(s'(G) \leq 2\Delta(G)\) if \(G\) is a \(p\)-expansion graph.
We introduce notions of \(k\)-chromatic uniqueness and \(k\)-chromatic equivalence in the class of all Sperner hypergraphs. They generalize the chromatic uniqueness and equivalence defined in the class of all graphs \([10]\) and hypergraphs \([2, 4, 8]\). Using some known facts, concerning a \(k\)-chromatic polynomial of a hypergraph \([5]\), a set of hypergraphs whose elements are \(3\)-chromatically unique is indicated. A set of hypergraphs characterized by a described \(3\)-chromatic polynomial is also shown. The application of the investigated notions can be found in \([5]\).
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\).
Let \(V\) denote the \(n\)-dimensional row vector space over a finite field \(\mathbb{F}_q\), and let \(W\) be a subspace of dimension \(n-d\). Let \(L(n,d) = \mathcal{P} \cup \{0\}\), where \({P} = \{A | A \text{ is a subspace of } V, A + W = V\}\). Partially ordered by ordinary or reverse inclusion, two families of finite atomic lattices are obtained. This article discusses their geometricity, and computes their characteristic polynomials.
A graph \(G\) is called \(H\)-equipackable if every maximal \(H\)-packing in \(G\) is also a maximum \(H\)-packing in \(G\). All \(M_2\)-equipackable graphs and \(P_3\)-equipackable graphs have been characterized. In this paper, \(P_k\)-equipackable paths, \(P_k\)-equipackable cycles, \(M_3\)-equipackable paths and \(M_3\)-equipackable cycles are characterized.
Let \(G\) be a graph with \(r\) vertices of degree at least two. Let \(H\) be any graph. Consider \(r\) copies of \(H\). Then \(G \oplus H\) denotes the graph obtained by merging the chosen vertex of each copy of \(H\) with every vertex of degree at least two of \(G\). Let \(T_0\) and \(T^{A_1}\) be any two caterpillars. Define the first attachment tree \(T_1 = T_0 \oplus T^{A_1}\). For \(i \geq 2\), define recursively the \((i^{th})\) attachment tree \(T_i = T_{i-1} \oplus T^{A_i}\), where \(T_{i-1}\) is the \((i-1)^{th}\) attachment tree. Here one of the penultimate vertices of \(T^{A_1}\), \(i \geq 1\) is chosen for merging with the vertices of degree at least two of \(T_{i-1}\), for \(i \geq 1\). In this paper, we prove that for every \(i \geq 1\), the \(i\)th attachment tree \(T_i\) is graceful and admits a \(\beta\)-valuation. Thus it follows that the famous graceful tree conjecture is true for this infinite class of \((i^{th})\) attachment trees \(T’_is\), for all \(i \geq 1\). Due to the results of Rosa \([21]\) and El-Zanati et al. \([5]\) the complete graphs \(K_{2cm+1}\) and complete bipartite graphs \(K_{qm,pm}\), for \(c,p,m,q \geq 1\) can be decomposed into copies of \(i\)th attachment tree \(T_i\), for all \(i \geq 1\), where \(m\) is the size of such \(i\)th attachment tree \(T_i\).
A packing of \(K_n\) with copies of \(C_4\) (the cycle of length \(4\)), is an ordered triple \((V, \mathcal{C}, L)\), where \(V\) is the vertex set of the complete graph \(K_n\), \(C\) is a collection of edge-disjoint copies of \(C_4\), and \(L\) is the set of edges not belonging to a block of \(\mathcal{C}\). The number \(n\) is called the order of the packing and the set of unused edges \(L\) is called the leave. If \(C\) is as large as possible, then \((V, \mathcal{C}, L)\) is called a maximum packing MPC\((n, 4, 1)\). We say that an handcuffed design \(H(v, k, 1)\) \((W, P)\) is embedded into an MPC\((n, 4, 1)\) \((V, C, L)\) if \(W \subseteq V\) and there is an injective mapping \(f : \mathcal{P} \to \mathcal{C}\) such that \(P\) is a subgraph of \(f(P)\) for every \(P \in \mathcal{P}\). Let \(\mathcal{SH}(n, 4, k)\) denote the set of the integers \(v\) such that there exists an MPC\((n, 4, 1)\) which embeds an \(H(v, k, 1)\). If \(n \equiv 1 \pmod 8\) then an MPC\((n, 4, 1)\) coincides with a \(4\)-cycle system of order \(n\) and \(\mathcal{SH}(n, 4, k)\) is found by Milici and Quattrocchi, Discrete Math., \(174 (1997)\).
The aim of the present paper is to determine \(\mathcal{SH}(n, 4, k)\) for every integer \(n \not\equiv 1 \pmod 8\), \(n \geq 4\).
Given a sequence \(X = (x_1, x_2, \ldots, x_k)\), let \(Y = (y_1, y_2, \ldots, y_k)\) be a sequence obtained by rearranging the terms of \(X\). The total self-variation of \(Y\) relative to \(X\) is \(\zeta_X(Y) = \sum_{i=1}^k |y_i – x_i|\). On the other hand, let \(G = (V, E)\) be a connected graph and \(\phi\) be a permutation of \(V\). The total relative displacement of \(\phi\) is \(\delta_\phi(G) = \sum_{\{x \neq y\}\subset V} |d(x, y) – d(\phi(x), \phi(y))|\), where \(d(v, w)\) means the distance between \(v\) and \(w\) in \(G\). It’s clear that the total relative displacement of \(\phi\) is a total self-variation relative to the distance sequence of the graph.
In this paper, we determine the sequences which attain the maximum value of the total self-variation of all possible rearrangements \(Y\) relative to \(X\). Applying this result to the distance sequence of a graph, we find a best possible upper bound for the total relative displacement of a graph.
Let \(G\) be a simple undirected graph. Denote by \(mi(G)\) the number of maximal independent sets in \(G\). In this paper, we determine the second and third largest number of maximal independent sets in trees. Extremal trees achieving these values are also determined.
In \([5]\), the first author posed the problem of determining the spectrum of \((K_4, K_4 – e)\)-designs. In this article, we solve this problem, and also determine the spectrum of \((K_4, K_4 – e)\)-designs with exactly one \(K_4\) (or, equivalently, the spectrum of \((K_4 – e)\)-designs with a hole of size \(4\)). We also improve the bound for embedding a partial \(S(2,4,v)\) into a \((K_4, K_4 – e)\)-design given in \([5]\).
Given a digraph \(D\), its competition graph \(C(D)\) has the same vertex set as \(D\) and an edge between two vertices \(x\) and \(y\) if there is a vertex \(u\) so that \((x,u)\) and \((y,u)\) are arcs of \(D\). Motivated by a problem of communications, Kim and Roberts [2002] studied the competition graphs of the special digraphs known as semiorders and the graphs arising as competition graphs of acyclic digraphs satisfying conditions so called \(C(p)\) or \(C^*(p)\). While they could completely characterize the competition graph of an acyclic digraph satisfying \(C(p)\), they obtained only partial results on \(C^*(p)\) and left the general case open. In this paper, we answer their open question.
A graph \(G\) is said to be well-covered if every maximal independent set of \(G\) is of the same size. It has been shown that characterizing well-covered graphs is a co-NP-complete problem. In an effort to characterize some of these graphs, different subclasses of well-covered graphs have been studied. In this paper, we will introduce the subclass of stable well-covered graphs, which are well-covered graphs that remain well-covered with the addition of any edge. Some properties of stable well-covered graphs are given. In addition, the relationships between stable well-covered graphs and some other subclasses of well-covered graphs, including the surprising equivalence between stable well-covered graphs and other known subclasses, are proved.
Let \(G\) be a graph with vertex set \(V(G)\). For any \(S \subseteq V(G)\), we use \(w(G – S)\) to denote the number of components of \(G – S\). The toughness of \(G\), \(t(G)\), is defined as \(t(G) = \min\left\{\frac{|S|}{w(G – S)} \mid S \subseteq V(G), w(G – S) > 1\right\}\) if \(G\) is not complete; otherwise, set \(t(G) = +\infty\). In this paper, we consider the relationship between the toughness and the existence of fractional \((g, f)\)-factors. It is proved that a graph \(G\) has a fractional \((g, f)\)-factor if \(t(G) \geq \frac{b^2 – 1}{a}\).
An almost-bipartite graph is a non-bipartite graph with the property that the removal of a particular single edge renders the graph bipartite. A graph labeling of an almost-bipartite graph \(G\) with \(n\) edges that yields cyclic \(G\)-decompositions of the complete graph \(K_{2nt+1}\) (i.e., cyclic \((K_{2nt+1}, G)\)-designs) was recently introduced by Blinco, El-Zanati, and Vanden Eynden. They called such a labeling a \(\gamma\)-labeling. Here we show that the class of almost-bipartite graphs obtained from \(C_m\) by adding an edge joining distinct vertices in the same part in the bipartition of \(V(C_{2m})\) has a \(\gamma\)-labeling if and only if \(m \geq 3\). This, along with results of Blinco and of Froncek, shows that if \(G\) is a graph of size \(n\) consisting of a cycle with a chord, then there exists a cyclic \((K_{2nt+1},G)\)-design for every positive integer \(t\).
For a given graph \(H\), a graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) is said to be potentially \(H\)-graphic if there is a realization of \(\pi\) containing \(H\) as a subgraph. In this paper, we characterize potentially \(K_{1,1,6}\)-positive graphic sequences. This characterization implies the value of \(\sigma(K_{1,1,6}, n)\). Moreover, we also give a simple sufficient condition for a positive graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) to be potentially \(K_{1,1,s}\)-graphic for \(n \geq s+2\) and \(s \geq 2\).
Let \(H(B)\) denote the space of all holomorphic functions on the unit ball \(B\). Let \(u \in H(B)\) and \(\varphi\) be a holomorphic self-map of \(B\). This paper characterizes the boundedness and compactness of the weighted composition operator \(uC_{\varphi}\), from Bloch-type spaces to weighted-type spaces in the unit ball.
Let \(G\) be a graph of order \(n\). Let \(a\) and \(b\) be integers with \(1 \leq a < b\), and let \(k \geq 2\) be a positive integer not larger than the independence number of \(G\). Let \(g(x)\) and \(f(x)\) be two non-negative integer-valued functions defined on \(V(G)\) such that \(a \leq g(x) \frac{(a+b)(k(a+b)-2)}{a+1}\) and \(|N_G(x_1) \cup N_G(x_2) \cup \cdots \cup N_G(x_k)| \geq \frac{(b-1)n}{a+b}\) for any independent subset \(\{x_1, x_2, \ldots, x_k\}\) of \(V(G)\). Furthermore, we show that the result is best possible in some sense.
A graph \(G\) is called quasi-claw-free if it satisfies the property:\(d(x,y) = 2 \Rightarrow \text{there exists} u \in N(x) \cap N(y) \text{ such that } N[u] \subseteq N[x] \cup N[y].\) It is shown that a Hamiltonian cycle can be found in polynomial time in four subfamilies of quasi-claw-free graphs.
We study near hexagons which satisfy the following properties:(i) every two points at distance 2 from each other are contained in a unique quad of order \((s,r_1)\) or \((s,r_2), r_1\neq r_2\); (ii) every line is contained in the same number of quads; (iii) every two opposite points are connected by the same number of geodesics. We show that there exists an association scheme on the point set of such a near hexagon and calculate the intersection numbers. We also show how the eigenvalues of the collinearity matrix and their corresponding multiplicities can be calculated. The fact that all multiplicities and intersection numbers are nonnegative integers gives restrictions on the parameters of the near hexagon. We apply this to the special case in which the near hexagon has big quads.
A perfect \(r\)-code in a graph is a subset of the graph’s vertices with the property that each vertex in the graph is within distance \(r\) of exactly one vertex in the subset. We determine the relationship between perfect \(r\)-codes in the lexicographic product of two simple graphs and perfect \(r\)-codes in each of the factors.
A graph \(G\) is called uniquely \(k\)-list colorable, or \(UkLC\) for short, if it admits a \(k\)-list assignment \(L\) such that \(G\) has a unique \(L\)-coloring. A graph \(G\) is said to have the property \(M(k)\) (\(M\) for Marshal Hall) if and only if it is not \(UkLC\). The \(m\)-number of a graph \(G\), denoted by \(m(G)\), is defined to be the least integer \(k\) such that \(G\) has the property \(M(k)\). After M. Mahdian and E.S. Mahmoodian characterized the \(U2LC\) graphs, M. Ghebleh and E.S. Mahmoodian characterized the \(U3LC\) graphs for complete multipartite graphs except for nine graphs in 2001. Recently, W. He et al. verified all the nine graphs are not \(U3LC\) graphs. Namely, the \(U3LC\) complete multipartite graphs are completely characterized. In this paper, complete multipartite graphs whose \(m\)-number are equal to \(4\) are researched and the \(U4LC\) complete multipartite graphs, which have at least \(6\) parts, are characterized except for finitely many of them. At the same time, we give some results about some complete multipartite graphs whose number of parts is smaller than \(6\).
A list-assignment \(L\) to the vertices of \(G\) is an assignment of a set \(L(v)\) of colors to vertex \(v\) for every \(v \in V(G)\). An \((L,d)^*\)-coloring is a mapping \(\phi\) that assigns a color \(\phi(v) \in L(v)\) to each vertex \(v \in V(G)\) such that at most \(d\) neighbors of \(v\) receive color \(\phi(v)\). A graph is called \((k,d)^*\)-choosable, if \(G\) admits an \((L,d)^*\)-coloring for every list assignment \(L\) with \(|L(v)| \geq k\) for all \(v \in V(G)\). In this note, it is proved that:(1) every toroidal graph containing neither adjacent \(3\)-cycles nor \(5\)-cycles, is \((3,2)^*\)-choosable;(2) every toroidal graph without \(3\)-cycles, is \((3,2)^*\)-choosable.
In this note, we consider a generalized Fibonacci sequence \(\{u_n\}\). Then we give a generating matrix for the terms of sequence \(\{u_{kn}\}\) for a positive integer \(k\). With the aid of this matrix, we derive some new combinatorial identities for the sequence \(\{u_{kn}\}\).
Let \(G = (V, E)\) be a graph. A subset \(S\) of \(V\) is called a dominating set of \(G\) if every vertex in \(V – S\) is adjacent to at least one vertex in \(S\). A global dominating set is a subset \(S\) of \(V\) which is a dominating set of both \(G\) as well as its complement \(\overline{G}\). The domination number (global domination number) \(\gamma(\gamma_g)\) of \(G\) is the minimum cardinality of a dominating set (global dominating set) of \(G\). In this paper, we obtain a characterization of bipartite graphs with \(\gamma_g = \gamma + 1\). We also characterize unicyclic graphs and bipartite graphs with \(\gamma_g = \alpha_0(G) + 1\), where \(\alpha_0(G)\) is the vertex covering number of \(G\).
In paper \([7]\), S. J. Xu and W. Jin proved that a cyclic group of order \(pq\), for two different odd primes \(p\) and \(q\), is a \(3\)-BCI-group, and a finite \(p\)-group is a weak \((p – 1)\)-BCI-group. As a continuation of their works, in this paper, we prove that a cyclic group of order \(2p\) is a \(3\)-BCI-group, and a finite \(p\)-group is a \((p – 1)\)-BCI-group.
Fifty-five new or improved lower bounds for \(A(n, d, w)\), the maximum possible number of binary vectors of length \(n\), weight \(w\), and pairwise Hamming distance no less than \(d\), are presented.
We give some estimates of the norm of weighted composition operators from \(\alpha\)-Bloch spaces to Bloch-type spaces on the unit ball in \(7\).
Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). The isolated toughness of \(G\) is defined as
\(I(G) = \min\left\{\frac{|S|}{i(G-S)}: S \subseteq V(G), i(G-S) \geq 2\right\}\)
if \(G\) is not complete. Otherwise, set \(I(G) = |V(G)| – 1\). Let \(a\) and \(b\) be positive integers such that \(1 \leq a \leq b\), and let \(g(x)\) and \(f(x)\) be positive integral-valued functions defined on \(V(G)\) such that \(a \leq g(x) \leq f(x) \leq b\). Let \(h(e) \in [0,1]\) be a function defined on \(E(G)\), and let \(d(x) = \sum_{e \in E_x} h(e)\) where \(E_x = \{xy : y \in V(G)\}\). Then \(d(x)\) is called the fractional degree of \(x\) in \(G\). We call \(h\) an indicator function if \(g(x) \leq d(x) \leq f(x)\) holds for each \(x \in V(G)\). Let \(E^h = \{e : e \in E(G), h(e) \neq 0\}\) and let \(G_h\) be a spanning subgraph of \(G\) such that \(E(G_h) = E^h\). We call \(G_h\) a fractional \((g,f)\)-factor. The main results in this paper are to present some sufficient conditions about isolated toughness for the existence of fractional \((g,f)\)-factors. If \(1 = g(x) < f(x) = b\), this condition can be improved and the improved bound is not only sharp but also a necessary and sufficient condition for a graph to have a fractional \([1,b]\)-factor.
Let \((G,C)\) be an edge-colored bipartite graph with bi-partition \((X,Y)\). A heterochromatic matching of \(G\) is such a matching in which no two edges have the same color. Let \(N^c(S)\) denote a maximum color neighborhood of \(S \subseteq V(G)\).
The spanning tree packing number of a connected graph \(G\), denoted by \(\tau(G)\), is the maximum number of edge-disjoint spanning trees of \(G\). In this paper, we determine the minimum number of edges that must be added to \(G\) so that the resulting graph has spanning tree packing number at least \(k\), for a given value of \(k\).
Let \(\gamma_{\overline{E}}\) and \(\gamma_{\overline{S}}\) be the minus edge domination and minus star domination numbers of a graph, respectively, and let \(\gamma_E\), \(\beta_1\), \(\alpha_1\) be the edge domination, matching, and edge covering numbers of a graph. In this paper, we present some bounds on \(\gamma_{\overline{E}}\) and \(\gamma_{\overline{S}}\) and characterize the extremal graphs of even order \(n\) attaining the upper bound \(\frac{n}{2}\) on \(\gamma_{\overline{E}}\). We also investigate the relationships between the above parameters.
The Wiener index of a connected graph is defined as the sum of all distances between unordered pairs of vertices. We determine the unicyclic graphs of given order, cycle length and number of pendent vertices with minimum Wiener index.
In this paper, by using the generating functions of Fibonacci polynomial sequences and their partial derivatives, we work out some identities involving the Fibonacci polynomials. As their primary applications, we obtain several identities involving the Fibonacci numbers and Lucas numbers.
Fukuda and Handa \([7]\) asked whether every even partial cube \(G\) is harmonic-even. It is shown that the answer is positive if the isometric dimension of \(G\) equals its diameter which is in turn true for partial cubes with isometric dimension at most \(6\). Under an additional technical condition it is proved that an even partial cube \(G\) is harmonic-even or has two adjacent vertices whose diametrical vertices are at distance at least \(4\). Some related open problems are posed.
By means of partial fraction decomposition, the purpose of this paper is to obtain a generalization of an algebraic identity which was given by Chu in \(\textit{The Electronic J. Camb.}\), \(11(2004), \#N15\).
Let \(G\) be a graph on \(n\) vertices \(v_1, v_2, \ldots, v_n\) and let \(d(v_i)\) be the degree of the vertex \(v_i\). If \((d(v_1), d(v_2), \ldots, d(v_n))^t\) is an eigenvector of the \((0,1)\)-adjacency matrix of \(G\), then \(G\) is said to be harmonic. A semi-regular harmonic graph is the harmonic graph which has exactly two different degrees. An equi-bipartite harmonic graph is the bipartite graph \(H = (X, Y; E)\) with \(|X| = |Y|\). In this paper, we characterize the semi-regular harmonic graph and equi-bipartite harmonic graph, and the degree sequence of equi-bipartite \(3\)-harmonic graphs.
We give necessary and sufficient conditions for a resolvable \(4\)-decomposition of \(AK_n\), in the case where \(H\) is one of the 10 graphs obtained by the union of two paths of length 2, with two possible exceptions. In particular, we complete the \(4\)-star (\(\lambda\)) and \(T\) (\(\tau\)) for higher \(\lambda\) and give complete solutions for resolvable decompositions into Fish (\(4\)-\(3\)), Mulinetto (\(hx\)) and Kites (\(BSI\)). In the cases of the Fish and Mulinetto the solution is obtained \(1\)-rotationally.
We note that with only a slight modification, Su’s proof on the fragments in \(k\)-critical \(n\)-connected graphs (see J. Graph Theory \(45 (2004), 281-297\)) can imply the following more general result: every non-complete \(W\)-locally \(k\)-critical \(n\)-connected graph has \(2k + 2\) distinct fragments \(F_1, F_2, \ldots, F_{2k+2}\) such that \(F_1 \cap W, F_2 \cap W, \ldots, F_{2k+2} \cap W\) are pairwise disjoint.
A packing of a graph \(G\) is a set of edge-disjoint \(4\)-cycles in \(G\) and a maximum packing of \(G\) with \(4\)-cycles is a packing which contains the largest number of \(4\)-cycles among all packings of \(G\). In this paper, we obtain the maximum packing of certain graphs such as \(K_{2m+1} – H\) where \(H\) is a \(2\)-regular subgraph, \(K_{2m} – F\) where \(F\) is a spanning odd forest of \(K_{2m}\), and \(2K_{2m} – L\) where \(L\) is a \(2\)-regular subgraph of \(2K_{2m}\).
In this paper, we consider the relationships between the second order linear recurrences, and the generalized doubly stochastic permanents and determinants.
An \(\lambda\)-design on \(v\) points is a set of \(v\) subsets (blocks) of a \(v\)-set such that any two distinct blocks meet in exactly \(\lambda\) points and not all of the blocks have the same size. Ryser’s and Woodall’s \(\lambda\)-design conjecture states that all \(\alpha\)-designs can be obtained from symmetric designs by a complementation procedure. In a previous paper, the author established feasibility criteria for the existence of \(\lambda\)-designs with two block sizes in the form of integrality conditions, equations, inequalities, and Diophantine equations involving various parameters of the designs. In that paper, these criteria and a computer were used to prove that the \(\lambda\)-design conjecture is true for all \(\lambda\)-designs with two block sizes with \(\lambda \leq 90\) and \(\lambda \neq 45\). In this paper, we extend these results and prove that the \(\lambda\)-design conjecture is also true for all \(\lambda\)-designs with two block sizes with \(\lambda = 45\) or \(91 \leq \alpha < 150\).
The binary linear code \(H^\bot_{m,2}\), \(m > 2\), of length \(\binom{m}{2}\) represented by the generator matrix \(H_{m,2}\) consisting of all distinct column strings of length \(m\) and Hamming weight \(2\) is considered. A parity-check matrix \(H^\bot_{m,2}\) is assigned to the code \(H^\bot_{m,2}\). The code \(H_{m,2,3}\), \(m > 3\), of length \(\binom{m}{2} + \binom{m}{3}\) represented by the parity-check matrix \(H_{m,2,3}\) consisting of all distinct column strings of length \(m\) and Hamming weight two or three is also considered. It is shown that \(H^\bot_{m,2}\) and \(H_{m,2,3}\) are optimal stopping redundancy codes, that is for each of these codes the stopping distance of the associated parity-check matrix is equal to the minimum Hamming distance of the code, and the rows of the parity-check matrix are linearly independent. Explicit formulas determining the number of stopping sets of arbitrary size for these codes are given.
For a finite group \(G\) and subsets \(T_1, T_2\) of \(G\), the Bi-Cayley digraph \(D = (V(D), E(D)) = D(G, T_1, T_2)\) of \(G\) with respect to \(T_1\) and \(T_2\) is defined as the bipartite digraph with vertex set \(V(D) = G \times \{0, 1\}\), and for \(g_1, g_2 \in G\), \(((g_1, 0), (g_2, 1)) \in E(D)\) if and only if \(g_2 = t_1 g_1\) for some \(t_1 \in T_1\), and \(((g_1, 1), (g_2, 0)) \in E(D)\) if and only if \(g_1 = t_2 g_2\) for some \(t_2 \in T_2\). If \(|T_1| = |T_2| = k\), then \(D\) is \(k\)-regular. In this paper, the spectra of Bi-Circulant digraphs are determined. In addition, some asymptotic enumeration theorems for the number of directed spanning trees in Bi-Circulant digraphs are presented.
The genus of a graph \(G\), denoted by \(\gamma(G)\), is the minimum genus of an orientable surface in which the graph can be embedded. In the paper, we use the Joint Tree Model to immerse a graph on the plane and obtain an associated polygon of the graph. Along the way, we construct a genus embedding of the edge disjoint union of \(K\) and \(H\), and solve Michael Stiebitz’s proposed conjecture: Let \(G\) be the edge disjoint union of a complete graph \(K\) and an arbitrary graph \(H\). Let \(H’\) be the graph obtained from \(H\) by contracting the set \(V(X)\) to a single vertex. Then
\[\gamma(K) + \gamma(H’) \leq \gamma(G).\]
We investigate brother avoiding round robin doubles tournaments and construct several infinite families. We show that there is a BARRDT(\(x\)) that is not a SAMDRR(\(n\)) for all \(n > 4\).
A digraph \(D(V, E)\) is said to be graceful if there exists an injection \(f: V(G) \to \{0, 1, \ldots, |E|\}\) such that the induced function \(f’: E(G) \to \{1, 2, \ldots, |E|\}\) which is defined by \(f'(u, v) = [f(v) – f(u)] \pmod{|E| + 1}\) for every directed edge \((u, v)\) is a bijection. Here, \(f\) is called a graceful labeling (graceful numbering) of \(D(V, E)\), while \(f’\) is called the induced edge’s graceful labeling of \(D\). In this paper, we discuss the gracefulness of the digraph \(n – \overrightarrow{C}_m\), and prove that \(n – \overrightarrow{C}_m\) is a graceful digraph for \(m = 4, 6, 8, 10\) and even \(n\).
In this note, we consider relative difference sets with the parameter \((m, 2, m-1, \frac{m-2}{2})\) in a group \(G\) relative to a subgroup \(N\). In the splitting case, \(G = H \times N\), we give a lower bound for the size of the commutator group \(H’\), and we show that \(H\) cannot have a homomorphic image which is generalized dihedral. In the non-splitting case, we prove that there is no \((2n, 2, 2n-1, n-1)\) relative difference set in a generalized dihedral group of order \(4n\), \(n > 1\).
Let \(P_n\) be a path with \(n\) vertices. \(P_n^k\), the \(k\)-th power of the path \(P_n\), is a graph on the same vertex set as \(P_n\), and the edges that join all vertices \(x\) and \(y\) if and only if the distance between them is at most \(k\). In this paper, the crossing numbers of \(P_n^k\) are studied. Drawings of \(P_n^k\) are presented and proved to be optimal for the case \(n \leq 8\) and for the case \(k \leq 4\).
A graph is said to be locally grid if the structure around each of its vertices is a \(3 x 3\) grid. As a follow up of the research initiated in \([8]\) and \([9]\) we prove that most locally grid graphs are uniquely determined by their Tutte polynomial.
Let \(P(G, \lambda)\) be the chromatic polynomial of a graph \(G\). A graph \(G\) is chromatically unique if for any graph \(H\), \(P(H, \lambda) = P(G, \lambda)\) implies \(H\) is isomorphic to \(G\). In his Ph.D. thesis, Zhao [Theorems 5.4.2 and 5.4.3] proved that for any positive integer \(t \geq 3\), the complete \(t\)-partite graphs \(K(p – k, p, p, \ldots, p)\) with \(p \geq k+2 \geq 4\) and \(K(p-k, p – 1, p, \ldots, p)\) with \(p \geq 2k \geq 4\) are chromatically unique. In this paper, by expanding the technique employed by Zhao, we prove that the complete \(t\)-partite graph \(K(p-k,\underbrace{ p -1, \ldots, p-1}, \underbrace{p, \ldots, p})\) is chromatically unique for integers \(p \geq k+2 \geq 4\) and \(t \geq d+3 \geq 3\).
We present a block diagonalization method for the adjacency matrices of two types of covering graphs. A graph \(Y\) is a covering graph of a base graph \(X\) if there exists an onto graph map \(\pi: Y \to X\) such that for each \(x \in X\) and for each \(y \in \{y \mid \pi(y) = x\}\), the collection of vertices adjacent to \(y\) maps onto the collection of vertices adjacent to \(x \in X\). The block diagonalization method requires the irreducible representations of the Galois group of \(Y\) over \(X\). The first type of covering graph is the Cayley graph over the finite ring \(\mathbb{Z}/p^n\mathbb{Z}\). The second type of covering graph resembles large lattices with vertices \(\mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}\) for large \(n\). For one lattice, the block diagonalization method allows us to obtain explicit formulas for the eigenvalues of its adjacency matrix. We use these formulas to analyze the distribution of its eigenvalues. For another lattice, the block diagonalization method allows us to find non-trivial bounds on its eigenvalues.
Broadcast domination in graphs is a variation of domination in which different integer weights are allowed on vertices and a vertex with weight \(k\) dominates its distance \(k\)-neighborhood. A distribution of weights on vertices of a graph \(G\) is called a dominating broadcast, if every vertex is dominated by some vertex with positive weight. The broadcast domination number \(\gamma_b(G)\) of a graph \(G\) is the minimum weight (the sum of weights over all vertices) of a dominating broadcast of \(G\). In this paper, we prove that for a connected graph \(G\), \(\gamma_b(G) \geq \lceil{2\text{rad}(G)}/{3}\rceil\). This general bound and a newly introduced concept of condensed dominating broadcast are used in obtaining sharp upper bounds for broadcast domination numbers of three standard graph products in terms of broadcast domination numbers of factors. A lower bound for a broadcast domination number of the Cartesian product of graphs is also determined, and graphs that attain it are characterized. Finally, as an application of these results, we determine exact broadcast domination numbers of Hamming graphs and Cartesian products of cycles.
The semigirth \(\gamma\) of a digraph \(D\) is a parameter related to the number of shortest paths in \(D\). In particular, if \(G\) is a graph, the semigirth of the associated symmetric digraph \(G^*\) is \(\ell(G^*) = \lfloor {g(G) – 1}/{2} \rfloor\), where \(g(G)\) is the girth of the graph \(G\). In this paper, some bounds for the minimum number of vertices of a \(k\)-regular digraph \(D\) having girth \(g\) and semigirth \(\ell\), denoted by \(n(k, g; \ell)\), are obtained. Moreover, we construct a family of digraphs which achieve the lower bound for some particular values of the parameters.
For a graph \(G\), let \(\mathcal{D}(G)\) be the set of all strong orientations of \(G\). Define the orientation number of \(G\), \(\overrightarrow{d}(G) = \min\{d(D) \mid D \in \mathcal{D}(G)\}\), where \(d(D)\) denotes the diameter of the digraph \(D\). In this paper, it has been shown that \(\overrightarrow{d}(G \times H) = d(G)\), where \(\times\) denotes the tensor product of graphs, \(H\) is a special type of circulant graph, and the diameter, \(d(G)\), of \(G\) is at least \(4\). Some interesting results have been obtained using this result. Further, it is shown that \(d(P_r \times K_s) = d(P_r)\) for suitable \(r\) and \(s\). Moreover, it is proved that \(\overrightarrow{d}(C_r \times K_s) = d(C_r)\) for appropriate \(r\) and \(s\).
We consider some partitions where even parts appear twice and some where evens do not repeat. Further, we offer a new partition theoretic interpretation of two mock theta functions of order \(8\).
A graph is said to be cordial if it has a \(0-1\) labeling that satisfies certain properties. The purpose of this paper is to generalize some known theorems and results of cordial graphs. Specifically, we show that certain combinations of paths, cycles, and stars are cordial.
An edge-magic total labeling on a graph with \(p\) vertices and \(q\) edges is defined as a one-to-one map taking the vertices and edges onto the integers \(1, 2, \ldots, p+q\) with the property that the sum of the labels on an edge and of its endpoints is constant, independent of the choice of edge. The magic strength of a graph \(G\), denoted by \(emt(G)\), is defined as the minimum of all constants over all edge-magic total labelings of \(G\). The maximum magic strength of a graph \(G\), denoted by \(eMt(G)\), is defined as the maximum constant over all edge-magic total labelings of \(G\). A graph \(G\) is called weak magic if \(eMt(G) – emt(G) > p\). In this paper, we study some classes of weak magic graphs.
In the first part of this paper, we present a generalization of complete graph factorizations obtained by labeling the graph vertices by natural numbers. In this generalization, the vertices are labeled by elements of an arbitrary group \(G\), in order to achieve a \(G\)-transitive factorization of the graph.
Vertex colorings of Steiner systems \(S(t,t+1,v)\) are considered in which each block contains at least two vertices of the same color. Necessary conditions for the existence of such colorings with given parameters are determined, and an upper bound of the order \(O(\ln v)\) is found for the maximum number of colors. This bound remains valid for nearly complete partial Steiner systems, too. In striking contrast, systems \(S(t,k,v)\) with \(k \geq t+2\) always admit colorings with at least \(c\cdot v^\alpha\) colors, for some positive constants \(c\) and \(\alpha\), as \(v\to\infty\).
Cwatsets were originally defined as subsets of \(\mathbb{Z}_2^d\) that are “closed with a twist.” Attempts have been made to generalize them, but the generalizations have failed to produce notions of subcwatset and quotient cwatset that behave naturally.
We present a new, abstract definition that appears to avoid these problems. The relationship between this new definition and its predecessor is similar to that between the abstract definition of “group” and its original meaning as a set of permutations. To justify the broader definition, we use small cancellation theory to prove a result analogous to the statement that every group is isomorphic to some permutation group. After developing the notion of a quotient cwatset, we prove an analogue of the First Homomorphism Theorem.
In this paper, we consider a class of recursively defined, full binary trees called Lucas trees and investigate their basic properties. In particular, the distribution of leaves in the trees will be carefully studied. We then go on to show that these trees are \(2\)-splittable, i.e., they can be partitioned into two isomorphic subgraphs. Finally, we investigate the total path length and external path length in these trees, the Fibonacci trees, and other full \(m\)-ary trees.
A tree \(T\) with \(n\) vertices and a perfect matching \(M\) is strongly graceful if \(T\) admits a graceful labeling \(f\) such that \(f(u)+f(v) = n-1\) for every edge \(uv \in M\). Broersma and Hoede \([5]\) conjectured that every tree containing a perfect matching is strongly graceful in \(1999\). We prove that a tree \(T\) with diameter \(D(T) \leq 5\) supports the strongly graceful conjecture on trees. We show several classes of basic seeds and some constructive methods for constructing large scales of strongly graceful trees.
In a previous paper, the first author introduced two classes of generalized Stirling numbers, \(s_m(n,k,p), S_m(n,k,p)\) with \(m = 1\) or \(2\), called \(p\)-Stirling numbers. In this paper, we discuss their determinant properties.
The Padmakar-Ivan (PI) index is a Wiener-Szeged-like topological index which reflects certain structural features of organic molecules. In this paper, we study the problem of PI index with respect to some simple pericondensed hexagonal systems and we solve it completely.
As a part of the author’s work of enumerating the edge-forwarding indices of Frobenius graphs, I give a class of valency four Frobenius graphs derived from the Frobenius groups \(\mathbb{Z}_{4n^2+1} \rtimes \mathbb{Z}_4\). Following the method of Fang, Li and Praeger, some properties including the diameter and the type of this class of graphs are given (Theorem \(3.2\)).
We address the problem of determining all sets which form minimal covers of maximal cliques for interval graphs. We produce an algorithm enumerating all minimal covers using the C-minimal elements of the interval order, as well as an independence Metropolis sampler. We characterize maximal removable sets, which are the complements of minimal covers, and produce a distinct algorithm to enumerate them. We use this last characterization to provide bounds on the maximum number of minimal covers for an interval order with a given number of maximal cliques, and present some simulation results on the number of minimal covers in different settings.
A directed triple system of order \(v\), denoted by DTS\((v)\), is a pair \((X,\mathcal{B})\) where \(X\) is a \(v\)-set and \(\mathcal{B}\) is a collection of transitive triples on \(X\) such that every ordered pair of \(X\) belongs to exactly one triple of \(\mathcal{B}\). A DTS\((v)\) is called pure and denoted by PDTS\((v)\) if \((x,y,z) \in \mathcal{B}\) implies \((z,y,x) \notin \mathcal{B}\). A large set of disjoint PDTS\((v)\) is denoted by LPDTS\((v)\). In this paper, we establish the existence of LPDTS\((v)\) for \(v \equiv 0,4 \pmod{6}\), \(v\geq 4\).
We extend and give short proofs of some recent results regarding some classes of rational difference equations.
The skewness \(sk(G)\) of a graph \(G = (V, E)\) is the smallest integer \(sk(G) \geq 0\) such that a planar graph can be obtained from \(G\) by the removal of \(sk(G)\) edges. The splitting number \(sp(G)\) of \(G\) is the smallest integer \(sp(G) \geq 0\) such that a planar graph can be obtained from \(G\) by \(sp(G)\) vertex splitting operations. The vertex deletion \(vd(G)\) of \(G\) is the smallest integer \(vd(G) \geq 0\) such that a planar graph can be obtained from \(G\) by the removal of \(vd(G)\) vertices. Regular toroidal meshes are popular topologies for the connection networks of SIMD parallel machines. The best known of these meshes is the rectangular toroidal mesh \(C_m \times C_n\), for which is known the skewness, the splitting number and the vertex deletion. In this work we consider two related families: a triangulation \(T_{m,n}\) of \(C_m \times C_n\) in the torus, and an hexagonal mesh \(H_{m,n}\), the dual of \(\mathcal{T}_{C_m\times C_n}\) in the torus. It is established that \(sp(T_{m,n}) = vd(T_{m,n}) = sk(H_{C_m\times C_n}) = sp(\mathcal{H}_{C_m\times C_n}) = vd(\mathcal{H}_{m,n}) = \min\{m,n\}\) and that \(sk(\mathcal{T}_{C_m\times C_n}) = 2\min\{m, n\}\).
Exploiting the empirical observation that the probability of \(k\) fixed points in a Welch-Costas permutation is approximately the same as in a random permutation of the same order, we propose a stochastic model for the most probable maximal number of fixed points in a Welch-Costas permutation.
Let \(\gamma_c(G)\)be the connected domination number of \(G\) and \(\gamma_t(G)\) be the tree domination number of \(G\). In this paper, we study the connected domination number and tree domination of \(P(n,k)\), and show that \(\gamma_{tr}(P(n, 4)) = \gamma_c(P(n, 4)) = n-1\) for \(n \geq 17\), \(\gamma_{tr}(P(n, 6)) = \gamma_c(P(n, 6)) = n-1\) for \(n \geq 25\), and \(\gamma_{tr}(P(n,8)) = \gamma_c(P(n,8)) = n-1\) for \(n \geq 33\).
A cut \((A, B)\) (where \(B = V – A\)) in a graph \(G = (V, E)\) is called internal if and only if there exists a vertex \(x \in A\) that is not adjacent to any vertex in \(B\) and there exists a vertex \(y \in B\) such that it is not adjacent to any vertex in \(A\). In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut \((A, B)\) in a chordal graph \(G\), there exists a clique with \(\kappa(G) + 1\) vertices (where \(\kappa(G)\) is the vertex connectivity of \(G\)) such that it is (approximately) bisected by the cut \((A, B)\). In fact, we give a stronger result: For any internal cut \((A, B)\) of a chordal graph, and for each \(i\), \(0 \leq i \leq \kappa(G) + 1\), there exists a clique \(K_i\) such that \(|A \cap K_i| = \kappa(G) + 1\), \(|A \cap K_i| = i\), and \(|B \cap K_i| = \kappa(G) + 1- i\).
An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be \(\Omega(k^2)\) where \(\kappa(G)\). Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least \(\frac{\kappa(G)(\kappa(G) + 1)}{2}\), where \(\kappa(G)\) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to \(\kappa(G)\). This result is tight.
We determine the automorphism group and the spectrum of the folded hypercube. In addition, we define the Bi-folded hypercube and determine its spectrum.
A connected graph \(G\) is said to be odd path extendable if for any odd path \(P\) of \(G\), the graph \(G – V(P)\) contains a perfect matching. In this paper, we at first time introduce the concept of odd path extendable graphs. Some simple necessary and sufficient conditions for a graph to be odd path extendable are given. In particular, we show that if a graph is odd path extendable, it is hamiltonian.
In this paper, we give one construction for constructing large harmonious graphs from smaller ones. Subsequently, three families of graphs are introduced and some members of them are shown to be or not to be harmonious.
A graph is called set reconstructible if it is determined uniquely (up to isomorphism) by the set of its vertex-deleted subgraphs. We prove that all graphs are set reconstructible if all \(2\)-connected graphs \(G\) with \(diam(G) = 2\) and all \(2\)-connected graphs \(G\) with \(diam(G) = diam(\overline{G}) = 3\) are set reconstructible.
A function \(f: V(G) \to \{-1,0,1\}\) defined on the vertices of a graph \(G\) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every \(v \in V\), \(f(N(v)) \geq 1\), where \(N(v)\) consists of every vertex adjacent to \(v\). The weight of a MTDF is the sum of its function values over all vertices. A MTDF \(f\) is minimal if there does not exist a MTDF \(g: V(G) \to \{-1,0,1\}\), \(f \neq g\), for which \(g(v) \leq f(v)\) for every \(v \in V\). The upper minus total domination number, denoted by \(\Gamma^{-}_{t}(G)\), of \(G\) is the maximum weight of a minimal MTDF on \(G\). A function \(f: V(G) \to \{-1,1\}\) defined on the vertices of a graph \(G\) is a signed total dominating function (STDF) if the sum of its function values over any open neighborhood is at least one. The signed total domination number, denoted by \(\gamma^{s}_{t}(G)\), of \(G\) is the minimum weight of a STDF on \(G\). In this paper, we establish an upper bound on \(\Gamma^{-}_{t}(G)\) of the 5-regular graph and characterize the extremal graphs attaining the upper bound. Also, we exhibit an infinite family of cubic graphs in which the difference \(\Gamma^{-}_t(G) – \gamma^{s}_t(G)\) can be made arbitrarily large.
Let \(G\) be a graph with vertex set \(V(G)\). An edge coloring \(C\) of \(G\) is called an edge-cover coloring, if for each color, the edges assigned with it form an edge cover of \(G\). The maximum positive integer \(k\) such that \(G\) has a \(k\)-edge-cover coloring is called the edge cover chromatic index of \(G\) and is denoted by \(\chi’_c(G)\). It is well known that \(\min\{d(v) – \mu(v) : v \in V(G)\} \leq \chi’_c(G) \leq \delta(G)\), where \(\mu(v)\) is the multiplicity of \(v\) and \(\delta(G)\) is the minimum degree of \(G\). If \(\chi’_c(G) = \delta(G)\), \(G\) is called a graph of CI class, otherwise \(G\) is called a graph of CII class. In this paper, we give a new sufficient condition for a nearly bipartite graph to be of CI class.
Though the well-known Vizing’s conjecture is not true for directed graphs in general, we show that it is true when the digraph and its reversal contain an efficient dominating set. In this paper, we investigate the existence of such sets in directed tori and infinite grids. We give a complete characterization of efficient dominating sets in the \(3\)-dimensional case and show the nonexistence of efficient \(d\)-dominating sets in directed tori for any \(d > 1\) and any dimension \(n > 1\).
For every two vertices \(u\) and \(v\) in a graph \(G\), a \(u-v\) geodesic is a shortest path between \(u\) and \(v\). Let \(I(u,v)\) denote the set of all vertices lying on a \(u-v\) geodesic. For a vertex subset \(S\), let \(I_G(S)\) denote the union of all \(I_G(u,v)\) for \(u,v \in S\). The geodetic number \(g(G)\) of a graph \(G\) is the minimum cardinality of a set \(S\) with \(I_G(S) = V(G)\). For a digraph \(D\), there is analogous terminology for the geodetic number \(g(D)\). The geodetic spectrum of a graph \(G\), denoted by \(S(G)\), is the set of geodetic numbers over all orientations of graph \(G\). The lower geodetic number is \(g^-(G) = \min S(G)\) and the upper geodetic number is \(g^+(G) = \max S(G)\). The main purpose of this paper is to investigate lower and upper geodetic numbers of graphs. Our main results in this paper are:
We estimate the essential norm of the weighted composition operator \(uC_{\varphi}\) from the weighted Bergman space \(A^{p}_{\alpha}(\mathbb{B})\) to the weighted space \(H^{\infty}_{\mu}(\mathbb{B})\) on the unit ball \(\mathbb{B}\), when \(p > 1\) and \(\alpha \geq -1\) (for \(\alpha = -1\), \(A^{p}_{\alpha}\) is the Hardy space \(H^{p}(\mathbb{B})\)). We also give a necessary and sufficient condition for the operator \(uC_{\varphi} : A^{p}_{\alpha}(\mathbb{B}) \to H^{\infty}_{\mu}(B)\) to be compact, and for the operator \(uC_{\varphi} : A^{p}_{\alpha}(\mathbb{B}) \to H^{\infty}_{\mu,0}(\mathbb{B})\) to be bounded or compact, when \(p > 0\), \(\alpha \geq -1\).
Let \(G = (V,E)\) be a graph. A set \(S \subseteq V\) is called a restrained dominating set of \(G\) if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V – S\). The restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the minimum cardinality of a restrained dominating set of \(G\). In this paper, we establish an upper bound on \(\gamma_r(G)\) for a connected graph \(G\) by the probabilistic method.
Any vertex labeling \(f: V \to \{0,1\}\) of the graph \(G = (V,E)\) induces a partial edge labeling \(f^*: E \to \{0,1\}\) defined by \(f^*(uv) = f(u)\) if and only if \(f(u) = f(v)\). The balance index set of \(G\) is defined as \(\{|f^{*{-1}}(0) – f^{*{-1}}(1)|: |f^{-1}(0) – f^{-1}(1)| \leq 1\}\). In this paper, we first determine the balance index sets of rooted trees of height not exceeding two, thereby completely settling the problem for trees with diameter at most four. Next we show how to extend the technique to rooted trees of any height, which allows us to derive a method for determining the balance index set of any tree.
We show that partial permutation decoding can be used, and give explicit \(s\)-PD-sets in the symmetric group, where \(s\) is less than the full error-correction capability of the code, for some classes of binary codes obtained from the adjacency matrices of the graphs with vertices the \(\binom{n}{3}\) \(3\)-subsets of a set of size \(n\) with adjacency defined by the vertices as \(3\)-sets being adjacent if they have a fixed number of elements in common.
Let \(G\) be a simple connected graph. For a subset \(S\) of \(V(G)\) with \(|S| = 2n + 1\), let \(\alpha_{(2n+1)}(G,S)\) denote the graph obtained from \(G\) by contracting \(S\) to a single vertex. The graph \(\alpha_{(2n+1)}(G, S)\) is also said to be obtained from \(G\) by an \(\alpha_{(2n+1)}\)-contraction. For pairwise disjoint subsets \(S_1, S_2, \ldots, S_{2n}\) of \(V(G)\), let \(\beta_n(G, S_1, S_2, \ldots, S_{2n})\) denote the graph obtained from \(G\) by contracting each \(S_i\) (\(i = 1, 2, \ldots, 2n\)) to a single vertex respectively. The graph \(\beta_{2n}(G, S_1, S_2, \ldots, S_{2n})\) is also said to be obtained from \(G\) by a \(\beta_{2n}\)-contraction. In the present paper, based on \(\alpha_{(2n+1)}\)-contraction and \(\beta_{2}\)-contraction, some new characterizations for \(n\)-extendable bipartite graphs are given.
A graph \(G\) is quasi-claw-free if it satisfies the property: \(d(x, y) = 2 \Rightarrow\) there exists \(u \in N(x) \cap N(y)\) such that \(N[u] \subseteq N[x] \cup N[y]\). In this paper, we prove that the circumference of a \(2\)-connected quasi-claw-free graph \(G\) on \(n\) vertices is at least \(\min\{3\delta + 2, n\}\) or \(G \in \mathcal{F}\), where \(\mathcal{F}\) is a class of nonhamiltonian graphs of connectivity \(2\). Moreover, we prove that if \(n \leq 40\), then \(G\) is hamiltonian or \(G \in \mathcal{F}\).
Let \(K_{n,n}\) denote the complete bipartite graph with \(n\) vertices in each part. In this paper, it is proved that there is no cyclic \(m\)-cycle system of \(K_{n,n}\) for \(m \equiv 2 \pmod{4}\) and \(n \equiv 2 \pmod{4}\). As a consequence, necessary and sufficient conditions are determined for the existence of cyclic \(m\)-cycle systems of \(K_{n,n}\) for all integers \(m \leq 30\).
We examine a design \(\mathcal{D}\) and a binary code \(C\) constructed from a primitive permutation representation of degree \(2025\) of the sporadic simple group \(M^c L\). We prove that \(\text{Aut}(C) = \text{Aut}(\mathcal{D}) = M^c L\) and determine the weight distribution of the code and that of its dual. In Section \(6\) we show that for a word \(w_i\) of weight \(7\), where \(i \in \{848, 896, 912, 972, 1068, 1100, 1232, 1296\}\) the stabilizer \((M^\circ L)_{w_i}\) is a maximal subgroup of \(M^\circ L\). The words of weight \(1024\) split into two orbits \(C_{(1024)_1}\) and \(C_{(1024)_2}\), respectively. For \(w_i \in C_{(1024)_1}\), we prove that \((M^c L)_{w_i}\) is a maximal subgroup of \(M^c L\).
Let \(\lambda K_v\) be the complete multigraph with \(v\) vertices, where any two distinct vertices \(x\) and \(y\) are joined by \(\lambda\) edges \(\{x,y\}\). Let \(G\) be a finite simple graph. A \(G\)-packing design (\(G\)-covering design) of \(K_v\), denoted by \((v, G, \lambda)\)-PD \(((v, G,\lambda)\)-CD), is a pair \((X, \mathcal{B})\), where \(X\) is the vertex set of \(K_v\), and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in at most (at least) \(\lambda\) blocks of \(\mathcal{B}\). A packing (covering) design is said to be maximum (minimum) if no other such packing (covering) design has more (fewer) blocks. In this paper, we have completely determined the packing number and covering number for the graphs with seven points, seven edges and an even cycle.
In this paper, it is shown that there are exactly \(5\) non-isomorphic abstract ovals of order \(9\), all of them projective. The result has been obtained via an exhaustive search, based on the classification of the \(1\)-factorizations of the complete graph with \(10\) vertices.
A graph \(G\) is said to be \(k\)-degenerate if for every induced subgraph \(H\) of \(G\), \(\delta(H) \leq k\). Clearly, planar graphs without \(3\)-cycles are \(3\)-degenerate. Recently, it was proved that planar graphs without \(5\)-cycles or without \(6\)-cycles are also \(3\)-degenerate. And for every \(k = 4\) or \(k \geq 7\), there exist planar graphs of minimum degree \(4\) without \(k\)-cycles. In this paper, it is shown that each \(C_7\)-free plane graph in which any \(3\)-cycle is adjacent to at most one triangle is \(3\)-degenerate. So it is \(4\)-choosable.
This paper investigates the embedding problem for resolvable group divisible designs with block size \(3\). The necessary and sufficient conditions are determined for all \(\lambda \geq 1\).
We provide combinatorial arguments of some relations between classical Stirling numbers of the second kind and two refinements of these numbers gotten by introducing restrictions to the distances among the elements in each block of a finite set partition.
We provide many new edge-magic and vertex-magic total labelings for the cycles \(C_{nk}\), where \(n \geq 3\) and \(k \geq 3\) are both integers and \(n\) is odd. Our techniques are of interest since known labelings for \(C_{k}\) are used in the construction of those for \(C_{nk}\). This provides significant new evidence for a conjecture on the possible magic constants for edge-magic and vertex-magic cycles.
A total dominating set of a graph \(G\) with no isolated vertex is a set \(S\) of vertices of \(G\) such that every vertex is adjacent to a vertex in \(S\). The total domination number of \(G\) is the minimum cardinality of a total dominating set in \(G\). In this paper, we present several upper bounds on the total domination number in terms of the minimum degree, diameter, girth, and order.
We denote by \((p, q)\)-graph \(G\) a graph with \(p\) vertices and \(q\) edges. An edge-magic total (EMT) labeling on a \((p,q)\)-graph \(G\) is a bijection \(\lambda: V(G) \cup E(G) \rightarrow [1,2,\ldots,p+q]\) with the property that, for each edge \(xy\) of \(G\), \(\lambda(x) + \lambda(xy) + \lambda(y) = k\), for a fixed positive integer \(k\). Moreover, \(\lambda\) is a super edge-magic total labeling (SEMT) if it has the property that \(\lambda(V(G)) = \{1, 2,\ldots,p\}\). A \((p,q)\)-graph \(G\) is called EMT (SEMT) if there exists an EMT (SEMT) labeling of \(G\). In this paper, we propose further properties of the SEMT graph. Based on these conditions, we will give new theorems on how to construct new SEMT (bigger) graphs from old (smaller) ones. We also give the SEMT labeling of \(P_n \cup P_{n+m}\) for possible magic constants \(k\) and \(m = 1, 2\),or \(3\).
A Kirkman packing design \(KPD({w, s^*, t^*}, v)\) is a Kirkman packing with maximum possible number of parallel classes, such that each parallel class contains one block of size \(s\), one block of size \(t\) and all other blocks of size \(w\). A \((k, w)\)-threshold scheme is a way of distributing partial information (shadows) to \(w\) participants, so that any \(k\) of them can determine a key easily, but no subset of fewer than \(k\) participants can calculate the key. In this paper, the existence of a \(KPD({3, 4^*, 5^*}, v)\) is established for every \(v \equiv 3 \pmod{6}\) with \(v \geq 51\). As its consequence, some new \((2, w)\)-threshold schemes have been obtained.
In this paper, we mainly define a semidirect product version of the Schützenberger product and also a new two-sided semidirect product construction for arbitrary two monoids. Then, as main results, we present a generating and a relator set for these two products. Additionally, to explain why these products have been defined, we investigate the regularity for the semidirect product version of Schützenberger products and the subgroup separability for this new two-sided semidirect product.
We consider the connected graphs with a unique vertex of maximum degree \(3\). Two subfamilies of such graphs are characterized and ordered completely by their indices. Moreover, a conjecture about the complete ordering of all graphs in this set is proposed.
Let \(G = (V(G), E(G))\) be a simple graph and \(T(G)\) be the set of vertices and edges of \(G\). Let \(C\) be a \(k\)-color set. A (proper) total \(k\)-coloring \(f\) of \(G\) is a function \(f: T(G) \rightarrow C\) such that no adjacent or incident elements of \(T(G)\) receive the same color. For any \(u \in V(G)\), denote \(C(u) = \{f(u)\} \cup \{f(uv) | uv \in E(G)\}\). The total \(k\)-coloring \(f\) of \(G\) is called the adjacent vertex-distinguishing if \(C(u) \neq C(v)\) for any edge \(uv \in E(G)\). And the smallest number of colors is called the adjacent vertex-distinguishing total chromatic number \(\chi_{at}(G)\) of \(G\). Let \(G\) be a connected graph. If there exists a vertex \(v \in V(G)\) such that \(G – v\) is a tree, then \(G\) is a \(1\)-tree. In this paper, we will determine the adjacent vertex-distinguishing total chromatic number of \(1\)-trees.
In this paper, we extend the study on packing and covering of complete directed graph \(D_t\) with Mendelsohn triples \([6]\). Mainly, the maximum packing of \(D_t-P\) and \(D_t\cup{P}\) with Mendelsohn triples are obtained respectively, where \(P\) is a vertex-disjoint union of directed cycles in \(D_t\).
In the theory of orthogonal arrays, an orthogonal array is called schematic if its rows form an association scheme with respect to Hamming distances. Which orthogonal arrays are schematic orthogonal arrays and how to classify them is an open problem proposed by Hedayat et al. \([12]\). In this paper, we study the Hamming distances of the rows in orthogonal arrays and construct association schemes according to the distances. The paper gives the partial solution of the problem by Hedayat et al. for symmetric and some asymmetric orthogonal arrays of strength two.
The Padmakar-Ivan \((PI)\) index is a Wiener-Szeged-like topological index which reflects certain structural features of organic molecules. In this paper, we study the PI index of gated amalgam.
The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. In this paper, we give formulae to calculate the nullity of \(n\)-vertex bicyclic graphs by means of the maximum matching number.
This note calculates the essential norm of a recently introduced integral-type operator from the Hilbert-Bergman weighted space \(A^2_\alpha(\mathbb{B}), \alpha \geq -1\) to a Bloch-type space on the unit ball \(\mathbb{B} \subset \mathbb{C}^n\).
Let \(G\) be a graph and let \(\sigma_k(G)\) be the minimum degree sum of an independent set of \(k\) vertices. For \(S \subseteq V(G)\) with \(|S| \geq k\), let \(\Delta_k(S)\) denote the maximum value among the degree sums of the subset of \(k\) vertices in \(S\). A cycle \(C\) of a graph \(G\) is said to be a dominating cycle if \(V(G \setminus C)\) is an independent set. In \([2]\), Bondy showed that if \(G\) is a \(2\)-connected graph with \(\sigma_3(G) \geq |V(G)| + 2\), then any longest cycle of \(G\) is a dominating cycle. In this paper, we improve it as follows: if \(G\) is a 2-connected graph with \(\Delta_3(S) \geq |V(G)| + 2\) for every independent set \(S\) of order \(\kappa(G) + 1\), then any longest cycle of \(G\) is a dominating cycle.
Let \(B\) be an \(m \times n\) array in which each symbol appears at most \(k\) times. We show that if \(k \leq \frac{n(n-1)}{8(m+n-2)} + 1\) then \(B\) has a transversal.
Let \(T\) be a partially ordered set whose Hasse diagram is a binary tree and let \(T\) possess a unique maximal element \(1_T\). For a natural number \(n\), we compare the number \(A_T^n\) of those chains of length \(n\) in \(T\) that contain \(1_T\) and the number \(B_T^n\) of those chains that do not contain \(1_T\). We show that if the depth of \(T\) is greater or equal to \(2n + [ n \log n ]\) then \(B_T^n > A_T^n\).
The boundedness and compactness of the weighted composition operator from logarithmic Bloch spaces to a class of weighted-type spaces are studied in this paper.
S.M. Lee proposed the conjecture: for any \(n > 1\) and any permutation \(f\) in \(S(n)\), the permutation graph \(P(P_n, f)\) is graceful. For any integer \(n > 1\), we discuss gracefulness of the permutation graphs \(P(P_n, f)\) when \(f = (123), (n-2, n-1, n), (i, i+1), 1 \leq i \leq n-1, (12)(34)\ldots(2m-1, 2m), 1 \leq m \leq \frac{n}{2}\), and give some general results.
A double-loop network (DLN) \(G(N;r,s)\) is a digraph with the vertex set \(V = \{0,1,\ldots, N-1\}\) and the edge set \(E=\{v \to v+r \pmod{N} \text{ and } v \to v+s \pmod{N} | v \in V\}\). Let \(D(N;r,s)\) be the diameter of \(G(N;r,s)\) and let us define \(D(N) = \min\{D(N;r,s) | 1 \leq r < s < N \text{ and } \gcd(N,r,s) = 1\}\), \(D_1(N) = \min\{D(N;1,s) | 1 < s 0\)). Coppersmith proved that there exists an infinite family of \(N\) for which the minimum diameter \(D(N) \geq \sqrt{3N} + c(\log N)^{\frac{1}{4}}\), where \(c\) is a constant.
In this paper, we consider cycle-partition problems which deal with the case when both vertices and edges are specified and we require that they should belong to different cycles. Minimum degree and degree sum conditions are given, which are best possible.
In this paper, we consider the relationships between the second order linear recurrences and the permanents and determinants of tridiagonal matrices.
We correct and improve results from a recent paper by G. Ren and U. Kahler, which characterizes the Bloch, the little Bloch and Besov space of harmonic functions on the unit ball \({B} \subset \mathbb{R}^n\).
Let \(G\) be a \(2\)-connected graph with maximum degree \(\Delta(G) \geq d\), and let \(x\) and \(z\) be distinct vertices of \(G\). Let \(W\) be a subset of \(V(G) \setminus \{x, z\}\) such that \(|W| \leq d – 1\). Hirohata proved that if \(\max\{d_G(u), d_G(v)\} \geq d\) for every pair of vertices \(u, v \in V(G) \setminus \{x, z\} \cup W\) such that \(d_G(u, v) = 2\), then \(x\) and \(z\) are joined by a path of length at least \(d – |W|\). In this paper, we show that if \(G\) satisfies the conditions of Hirohata’s theorem, then for any given vertex \(y\) such that \(d_G(y) \geq d\), \(x\) and \(z\) are joined by a path of length at least \(d – |W|\) which contains \(y\).
For any positive integer \(k\), there exists a smallest positive integer \(N\), depending on \(k\), such that every \(2\)-coloring of \(1, 2, \ldots, N\) contains a monochromatic solution of the equation \(x + y + kz = 3w\). Based on computer checks, Robertson and Myers in \([5]\) conjectured values for \(N\) depending on the congruence class of \(k\) (mod \(9\)). In this note, we establish the values of \(N\) and find that in some cases they depend on the congruence class of \(k\) (mod \(27\)).
The support of a matrix \(M\) is the \((0, 1)\)-matrix with \(ij\)-th entry equal to \(1\) if the \(ij\)-th entry of \(M\) is non-zero, and equal to \(0\), otherwise. The digraph whose adjacency matrix is the support of \(M\) is said to be the digraph of \(M\). In this paper, we observe some general properties of digraphs of unitary matrices.
The \(k\)-restricted total domination number of a graph \(G\) is the smallest integer \(t_k\), such that given any subset \(U\) of \(k\) vertices of \(G\), there exists a total dominating set of \(G\) of cardinality at most \(t\), containing \(U\). Hence, the \(k\)-restricted total domination number of a graph \(G\) measures how many vertices are necessary to totally dominate a graph if an arbitrary set of \(k\) vertices are specified to be in the set. When \(k = 0\), the \(k\)-restricted total domination number is the total domination number. For \(1 \leq k \leq n\), we show that \(t_k \leq 4(n + k)/7\) for all connected graphs of order \(n\) and minimum degree at least two and we characterize the graphs achieving equality. These results extend earlier results of the author (J. Graph Theory \(35 (2000), 21-45)\). Using these results we show that if \(G\) is a connected graph of order \(n\) with the sum of the degrees of any two adjacent vertices at least four, then \(\gamma_t(G) \leq 4n/7\) unless \(G \in \{C_3, C_5, C_6, C_{10}\}\).
The Szeged index of a graph \(G\) is defined as \(\text{Sz}(G) = \sum_{e=uv \in E(G)} N_u(e|G) N_v(e|G)\), where \(N_u(e|G)\) is the number of vertices of \(G\) lying closer to \(u\) than to \(v\) and \(N_v(e|G)\) is the number of vertices of \(G\) lying closer to \(v\) than to \(u\). In this article, the Szeged index of some hexagonal systems applicable in nanostructures is computed.
In this paper, we consider the class of impartial combinatorial games for which the set of possible moves strictly decreases. Each game of this class can be considered as a domination game on a certain graph, called the move-graph. We analyze this equivalence for several families of combinatorial games, and introduce an interesting graph operation called iwin and match that preserves the Grundy value. We then study another game on graphs related to the dots and boxes game, and we propose a way to solve it.
Let \(C_n\) denote the cycle with \(n\) vertices, and \(C_n^{(t)}\) denote the graphs consisting of \(t\) copies of \(C_n\), with a vertex in common. Koh et al. conjectured that \(C_n^{(t)}\) is graceful if and only if \(nt \equiv 0,3 \pmod{4}\). The conjecture has been shown true for \(n = 3,5,6,7,9,11,4k\). In this paper, the conjecture is shown to be true for \(n = 13\).
This paper deals with a connection between the universal circuits matrix \([10]\) and the crossing relation \([1,5]\). The value of the universal circuits matrix obtained for \(\overline{\omega}\), where \(\omega\) is an arbitrary feedback function that generates de Bruijn sequences, forms the binary matrix that represents the crossing relation of \(\omega\). This result simplifies the design and study of the feedback functions that generate the de Bruijn sequences and allows us to decipher many inforrnations about the adjacency graphs of another feedback functions. For example, we apply these results to analyze the Hauge-Mykkeltveit classification of a family of de Bruijn sequences \([4]\).
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 \(et.\; al [7]\) proved 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 we show that for a given \(k\) and for all \(n < 3k\) and \(r \geq 2(k – 1)\), \(d(n, r, \chi = k) = k-1\).
A two-colored digraph \(D\) is primitive if there exist nonnegative integers \(h\) and \(k\) with \(h+k > 0\) such that for each pair \((i,j)\) of vertices there exists an \((h, k)\)-walk in \(D\) from \(i\) to \(j\). The exponent of the primitive two-colored digraph \(D\) is the minimum value of \(h + k\) taken over all such \(h\) and \(k\). In this paper, we consider the exponents of families of two-colored digraphs of order \(n\) obtained by coloring the digraph that has the exponent \((n – 1)^2\). We give the tight upper bound on the exponents, and the characterization of the extremal two-colored digraph.
A graceful labeling of a graph \(G\) with \(m\) edges is a function \(f: V(G) \to \{0, \ldots, m\}\) such that distinct vertices receive distinct numbers and \(\{|f(u) – f(v)|: uv \in E(G)\} = \{1, \ldots, m\}\). A graph is graceful if it has a graceful labeling. In \([1]\) this question was posed: “Is there an \(n\)-chromatic graceful graph for \(n \geq 6\)?”. In this paper it is shown that for any natural number \(n\), there exists a graceful graph \(G\) with \(\chi(G) = n\).
A connected graph \(G = (V, E)\) is said to be \((a, d)\)-antimagic, for some positive integers \(a\) and \(d\), if its edges admit a labeling by all the integers in the set \(\{1, 2, \ldots, |E(G)|\}\) such that the induced vertex labels, obtained by adding all the labels of the edges adjacent to each vertex, consist of an arithmetic progression with the first term \(a\) and the common difference \(d\). Mirka Miller and Martin Ba\'{e}a proved that the generalized Petersen graph \(P(n, 2)\) is \((\frac{3n+3}{2}, 3)\)-antimagic for \(n \equiv 0 \pmod{4}\), \(n \geq 8\) and conjectured that \(P(n, k)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n\) and \(2 \leq k \leq \frac{n}{2}-1\). The first author of this paper proved that \(P(n, 3)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n \geq 6\). In this paper, we show that the generalized Petersen graph \(P(n, 2)\) is \((\frac{3n+6}{2} , 3)\)-antimagic for \(n \equiv 2 \pmod{4}\), \(n \geq 10\).
Let \(0 \leq p \leq [\frac{r+1}{2}]\) and \(\sigma(K_{r+1}^{-p},n)\) be the smallest even integer such that each \(n\)-term graphic sequence with term sum at least \(\sigma(K_{r+1}^{-p},n)\) has a realization containing \(K_{r+1}^{-p}\) as a subgraph, where \(K_{r+1}^{-p}\) is a graph obtained from a complete graph \(K_{r+1}\) on \(r+1\) vertices by deleting \(p\) edges which form a matching. In this paper, we determine \(\sigma(K_{r+1}^{-p},n)\) for \(r \geq 2, 1 \leq p \leq [\frac{r+1}{2}]\) and \(n \geq 3r + 3\). As a corollary, we also determine \(\sigma(K_{1^*,2^t}n)\) for \(t \geq 1\) and \(n \geq 3s + 6t\), where \(K_{1^*,2^t}\) is an \(r_1\times r_2\times \ldots \times r_{s+t}\) complete \((s + t)\)-partite graph with \(r_1 = r_2 = \ldots = r_s = 1\) and \(r_{s+1} = r_{s+2} = \ldots = r_{s+t} = 2\) and \(\sigma(K_{1^*,2^t},n)\) is the smallest even integer such that each \(n\)-term graphic sequence with term sum at least \(\sigma(K_{1^*,2^t},n)\) has a realization containing \(K_{1^*,2^t}\) as a subgraph.
Let \(n, s_1\) and \(s_2\) be positive integers such that \(1 \leq s_1 \leq n/2, 1 \leq s_2 \leq n/2, s_1 \neq s_2\) and \(gcd(n, s_1, s_2) = 1\). An undirected double-loop network \(G(n;\pm s_1,\pm s_2)\) is a graph \((V, E)\), where \(V = \mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}\), and \(E = \{(i \to i+s_1 \mod n), (i\to i-s_1 \mod n), (i\to i+s_2 \mod n), (i\to i-s_2 \mod n) | i = 0, 1, 2, \ldots, n-1\}\). In this paper, a diameter formula is given for an undirected double-loop network \(G(n; \pm s_1, \pm s_2)\). As its application, two new optimal families of undirected double-loop networks are presented.
Anthony J. Macula constructed a \(d\)-disjunct matrix \(\delta(n,d,k)\) in \([1]\), and we now know it is determined by one type of pooling space. In this paper, we give some properties of \(\delta(n,d,k)\) and its complement \(\delta^c(n,d,k)\).
Let \(S\) be a primitive non-powerful signed digraph. The base \(l(S)\) of \(S\) is the smallest positive integer \(l\) such that for all ordered pairs of vertices \(i\) and \(j\) (not necessarily distinct), there exists a pair of \(SSSD\) walks of length \(t\) from \(i\) to \(j\) for each integer \(t \geq l\). In this work, we use \(PNSSD\) to denote the class of all primitive non-powerful signed symmetric digraphs of order \(n\) with at least one loop. Let \(l(n)\) be the largest value of \(l(S)\) for \(S \in\) \(PNSSD\), and \(L(n) = \{l(S) | S \in PNSSD\}\). For \(n \geq 3\), we show \(L(n) = \{2, 3, \ldots, 2n\}\). Further, we characterize all primitive non-powerful signed symmetric digraphs of order \(n\) with at least one loop whose bases attain \(l(n)\).
For a graph \(G = (V, E)\) and a binary labeling \(f : V(G) \to \mathbb{Z}_2\), let \(v_f(i) = |f^{-1}(1)|\). The labeling \(f\) is said to be friendly if \(|v_f(1) – v_f(0)| \leq 1\). Any vertex labeling \(f : V(G) \to \mathbb{Z}_2\) induces an edge labeling \(f^* : E(G) \to \mathbb{Z}_2\) defined by \(f^*(xy) =| f(x) – f(y)|\). Let \(e_f(i) = |f^{*-1}(i)|\). The friendly index set of the graph \(G\), denoted by \(FI(G)\), is defined by
\[FI(G) = \{|e_f(1) – e_f(0)| : f \text{ is a friendly vertex labeling of } G\}.\]
In \([15]\) Lee and Ng conjectured that the friendly index sets of trees will form an arithmetic progression. This conjecture has been mentioned in \([17]\) and other manuscripts. In this paper, we will first determine the friendly index sets of certain caterpillars of diameter four. Then we will disprove the conjecture by presenting an infinite number of trees whose friendly index sets do not form an arithmetic progression.
Let \(S\) be a primitive non-powerful signed digraph of order \(n\). The base of a vertex \(u\), denoted by \(l_S(u)\), is the smallest positive integer \(l\) such that there is a pair of SSSD walks of length \(i\) from \(u\) to each vertex \(v \in V(S)\) for any integer \(t \geq l\). We choose to order the vertices of \(S\) in such a way that \(l_S(1) \leq l_S(2) \leq \ldots \leq l_S(n)\), and call \(l_S(k)\) the \(k\)th local base of \(S\) for \(1 \leq k \leq n\). In this work, we use PNSSD to denote the class of all primitive non-powerful signed symmetric digraphs of order \(n\) with at least one loop. Let \(l(k)\) be the largest value of \(l_S(k)\) for \(S \in\) PNSSD, and \(L(k) = \{l_S(k) | S \in PNSSD\}\). For \(n \geq 3\) and \(1 \leq k \leq n-1\), we show \(I(k) = 2n – 1\) and \(L(k) = \{2, 3, \ldots, 2n-1\}\). Further, we characterize all primitive non-powerful signed symmetric digraphs whose \(k\)th local bases attain \(I(k)\).
Let \(\mathcal{U}_n(k)\) denote the set of all unicyclic graphs on \(n\) vertices with \(k\) (\(k \geq 1\)) pendant vertices. Let \(\diamondsuit_4^k\) be the graph on \(n\) vertices obtained from \(C_4\) by attaching \(k\) paths of almost equal lengths at the same vertex. In this paper, we prove that \(\diamondsuit_4^k\) is the unique graph with the largest Laplacian spectral radius among all the graphs in \(\mathcal{U}_n(k)\), when \(n \geq k + 4\).
For graphs \(G_1, G_2, \ldots, G_m\), the Ramsey number \(R(G_1, G_2, \ldots, G_m)\) is defined to be the smallest integer \(n\) such that any \(m\)-coloring of the edges of the complete graph \(K_n\) must include a monochromatic \(G_i\) in color \(i\), for some \(i\). In this note, we establish several lower and upper bounds for some Ramsey numbers involving quadrilateral \(C_4\), including:\(R(C_4, K_9) \leq 32,
19 \leq R(C_4, C_4, K_4)\leq 22, 31 \leq R(C_4, C_4, C_4, K_4) \leq 50, 52 \leq R(C_4, K_4, K_4) \leq 72, 42 \leq R(C_4, C_4, K_3, K_5) \leq 76, 87\leq R(C_4, C_4, K_4, K_4) \leq 179.\)
We consider the problem of determining the \(Q\)-integral graphs, i.e., the graphs with integral signless Laplacian spectrum. First, we determine some infinite series of such graphs having the other two spectra (the usual one and the Laplacian) integral. We also completely determine all \((2, s)\)-semiregular bipartite graphs with integral signless Laplacian spectrum. Finally, we give some results concerning \((3, 4)\) and \((3, 5)\)-semiregular bipartite graphs with the same property.
Let \(G\) be a connected graph. For any two vertices \(u\) and \(v\), let \(d(u, v)\) denote the distance between \(u\) and \(v\) in \(G\). The maximum distance between any pair of vertices is called the diameter of \(G\) and denoted by \(diam(G)\). A radio-labeling (or multi-level distance labeling) with span \(k\) for \(G\) is a function \(f\) that assigns to each vertex a label from the set \(\{0, 1, 2, \ldots, k\}\) such that the following holds for any vertices \(u\) and \(v\): \(|f(u) – f(v)| \geq diam(G) – d(u, v) + 1\). The radio number of \(G\) is the minimum span over all radio-labelings of \(G\). The square of \(G\) is a graph constructed from \(G\) by adding edges between vertices of distance two apart in \(G\). In this article, we completely determine the radio number for the square of any path.
Let \(G\) be a simple connected graph containing a perfect matching. \(G\) is said to be BM-extendable if every matching \(M\) whose induced subgraph is a bipartite graph extends to a perfect matching of \(G\). In this paper, for recognizing BM-extendable graphs, we present some conditions in terms of vertex degrees, including the degree sum conditions, the minimum degree conditions, and the Fan-type condition. Furthermore, we show that all these conditions are best possible in some sense.
Let \(u\) be an odd vertex of a bipartite graph \(B\) and suppose that \(f : V(B) \to \mathbb{N}\) is a function such that \(f(u) = \left\lceil d_B(u)/2 \right\rceil\) and \(f(v) = \left\lceil d_B(v)/2 \right\rceil + 1\) for \(v \in V(B) \setminus u\), where \(d_B(v)\) is the degree of \(v\) in \(B\). In this paper, we prove that \(B\) is \(f\)-choosable.
An arc-colored digraph \(D\) is called alternating whenever \(\{(u, v), (v, w)\} \subseteq A(D)\) implies that the color assigned to \((u, v)\) is different from the color of \((v, w)\). In arc-colored digraphs, a set of vertices \(N\) is said to be a kernel by alternating paths whenever it is an independent and dominating set by alternating directed paths (there is no alternating directed path between every pair of its vertices and for every vertex not in \(N\), there exists an alternating path from it to some vertex in \(N\)). With this new concept, we generalize the concept of kernel in digraphs. In this paper, we prove the existence of alternating kernels in possibly infinite arc-colored digraphs with some coloration properties. We also state a bilateral relation between the property of every induced subdigraph of an arc-colored digraph \(D\) of having a kernel by alternating paths and the property of every induced subdigraph of the non-colored digraph \(D\) of having a kernel, with this we enounce several sufficient conditions for \(D\) to have an alternating kernel. Previous results on kernels are generalized.
In this paper, we present a new simple linear-time algorithm for determining the number of spanning trees in the class of complement reducible graphs, also known as cographs. For a cograph \(G\) on \(n\) vertices and \(m\) edges, our algorithm computes the number of spanning trees of \(G\) in \(O(n + m)\) time and space, where the complexity of arithmetic operations is measured under the uniform cost criterion. The algorithm takes advantage of the cotree of the input cograph \(G\) and works by contracting it in a bottom-up fashion until it becomes a single node. Then, the number of spanning trees of \(G\) is computed as the product of a collection of values which are associated with the vertices of \(G\) and are updated during the contraction process. The correctness of our algorithm is established through the Kirchhoff matrix tree theorem, and also relies on structural and algorithmic properties of the class of cographs. We also extend our results to a proper superclass of cographs, namely the \(P_4\)-reducible graphs, and show that the problem of finding the number of spanning trees of a \(P_4\)-reducible graph has a linear-time solution.
This paper extends the concept of paving from finite matroids to matroids of arbitrary cardinality. Afterwards, a paving matroid of arbitrary cardinality is characterized in terms of its collection of closed sets, independent sets, and circuits, respectively.
A Hamiltonian walk in a connected graph \(G\) is a closed walk of minimum length which contains every vertex of \(G\). The Hamiltonian number \(h(G)\) of a connected graph \(G\) is the length of a Hamiltonian walk in \(G\). Let \(\mathcal{G}(n)\) be the set of all connected graphs of order \(n\), \(\mathcal{G}(n, \kappa = k)\) be the set of all graphs in \(\mathcal{G}(n)\) having connectivity \(\kappa = k\), and \(h(n,k) = \{h(G) : G \in \mathcal{G}(n, \kappa = k)\}\). We prove in this paper that for any pair of integers \(n\) and \(k\) with \(1 \leq k \leq n – 1\), there exist positive integers \(a := \min(h;n,k)) = \min\{h(G) : G \in \mathcal{G}(n, \kappa = k)\}\) and \(b := \max(h;n,k)) = \max\{h(G) : G \in \mathcal{G}(n, \kappa = k)\}\) such that \((h;n,k) = \{x \in \mathbb{Z} : a \leq x \leq b\}\). The values of \(\min(h;n,k))\) and \(\max(h(n,k))\) are obtained in all situations.
A well-known result on matchings of graphs is that the intersection of all maximal barriers is equal to the “set A” in the Gallai-Edmonds decomposition. In this paper, we give a generalization of this result to the framework of path-matchings introduced by Cunningham and Geelen. Furthermore, we present a sufficient condition for a graph to have a perfect path-matching.
This paper describes some new methods of constructing rectangular designs from balanced incomplete block (BIB) designs and Hadamard matrices. At the end of the paper, a table of rectangular designs in the range of \(r\),\(k \leq 15\) is given.
An \(n \times n\) sign pattern \(A\) is a spectrally arbitrary pattern if for any given real monic polynomial \(f(x)\) of degree \(n\), there is a real matrix \(B \in Q(A)\) having characteristic polynomial \(f(x)\). In this paper, we give two new classes of \(n \times n\) spectrally arbitrary sign patterns which are generalizations of the pattern \(W_{n}(k)\) defined in [T. Britz, J.J. McDonald, D.D. Olesky, P. van den Driessche, Minimal spectrally arbitrary sign patterns, SIAM Journal on Matrix Analysis and Applications, \(26(2004), 257-271]\).
We show that the power subgroups \(M^{6k}\) (\(k > 1\)) of the Modular group \(M = \text{PSL}(2, \mathbb{Z})\) are subgroups of the groups \(M'(6k, 6k)\). Here, the groups \(M'(6k, 6k)\) (\(k > 1\)) are subgroups of the commutator subgroup \(M’\) of \(M\) of index \(36k^2\) in \(M’\).
Let \(G\) be a simple graph. The double vertex graph \(U_2(G)\) of \(G\) is the graph whose vertex set consists of all \(2\)-subsets of \(V(G)\) such that two distinct vertices \(\{x,y\}\) and \(\{u,v\}\) are adjacent if and only if \(|\{x,y\} \cap \{u,v\}| = 1\) and if \(x = u\), then \(y\) and \(v\) are adjacent in \(G\). In this paper, we consider the exponents and primitivity relationships between a simple graph and its double vertex graph. A sharp upper bound on exponents of double vertex graphs of primitive simple graphs and the characterization of extremal graphs are obtained.
Let \(S_n\) be the set of permutations on \(\{1, \ldots, n\}\) and \(\pi \in S_n\). Let \(d(\pi)\) be the arithmetic average of \(\{|i – \pi(i)| : 1 \leq i \leq n\}\). Then \(d(\pi)/n \in [0, 1/2]\), the expected value of \(d(\pi)/n\) approaches \(1/3\) as \(n\) approaches infinity, and \(d(\pi)/n\) is close to \(1/3\) for most permutations. We describe all permutations \(\pi\) with maximal \(d(\pi)\).
Let \(s^+(\pi)\) and \(s^*(\pi)\) be the arithmetic and geometric averages of \(\{|\pi(i) – \pi(i + 1)| : 1 \leq i 1\). We describe all permutations \(\pi\),\(\sigma\) with maximal \(s^+(\pi)\) and \(s^*(\sigma)\).
A connected graph \(G = (V,E)\) is said to be \((a,d)\)-antimagic, for some positive integers \(a\) and \(d\), if its edges admit a labeling by all the integers in the set \(\{1, 2, \ldots, |E(G)|\}\) such that the induced vertex labels, obtained by adding all the labels of the edges adjacent to each vertex, consist of an arithmetic progression with the first term \(a\) and the common difference \(d\). Mirka Miller and Martin Bača proved that the generalized Petersen graph \(P(n,2)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for \(n \equiv 0 \pmod{4}\), \(n \geq 8\), and conjectured that \(P(n, k)\) is \((\frac{5n+5}{2}, 2)\)-antimagic for odd \(n\) and \(2 \leq k \leq \frac{n}{2}-1\). In this paper, we show that the generalized Petersen graph \(P(n,2)\) is \((\frac{5n+5}{2}, 2)\)-antimagic for \(n \equiv 3 \pmod{4}\), \(n \geq 7\).
Sierpiński graphs \(S(n,k)\), \(n, k \in \mathbb{N}\), can be interpreted as graphs of a variant of the Tower of Hanoi with \(k \geq 3\) pegs and \(n \geq 1\) discs. In particular, it has been proved that for \(k = 3\) the graphs \(S(n, 3)\) are isomorphic to the Hanoi graphs \(H_3^n\). In this paper, we will determine the chromatic number, the diameter, the eccentricity of a vertex, the radius, and the centre of \(S(n,k)\). Moreover, we will derive an important invariant and a number-theoretical characterization of \(S(n,k)\). By means of these results, we will determine the complexity of Problem \(1\), that is, the complexity of getting from an arbitrary vertex \(v \in S(n,k)\) to the nearest and to the most distant extreme vertex. For the Hanoi graphs \(H_3^n\), some of these results are new.
In this paper, we will prove that there exist no \([n,k,d]_q\) codes of \(sq^{k-1}-(s+t)q^{k-2}-q^{k-4} \leq d \leq sq^{k-1}-(s+t)q^{k-2}\) attaining the Griesmer bound with \(k \geq 4, 1 \leq s \leq k-2, t \geq 1\), and \(s+t \leq (q+1)\backslash 2\). Furthermore, we will prove that there exist no \([n,k,d]_q\) codes for \(sq^{k-1}-(s+t)q^{k-2}-q^{k-3} \leq d \leq s\) attaining the Griesmer bound with \(k \geq 3\), \(1 \leq s \leq k-2\), \(t \geq 1\), and \(s+t \leq \sqrt{q}-1\). The results generalize the nonexistence theorems of Tatsuya Maruta (see \([7]\)) and Andreas Klein (see \([4]\)) to a larger class of codes.
We study the spectral radius of graphs with \(n\) vertices and a \(k\)-vertex cut and describe the graph which has the maximal spectral radius in this class. We also discuss the limit point of the maximal spectral radius.
Consider lattice paths in \(\mathbb{Z}^2\) taking unit steps north (N) and east (E). Fix positive integers \(r,s\) and put an equivalence relation on points of \(\mathbb{Z}^2\) by letting \(v,w\) be equivalent if \(v-w = \ell(r,s)\) for some \(k \in \mathbb{Z}\). Call a lattice path \({valid}\) if whenever it enters a point \(v\) with an E-step, then any further points of the path in the equivalence class of \(v\) are also entered with an E-step. Loehr and Warrington conjectured that the number of valid paths from \((0,0)\) to \((nr,ns)\) is \({\binom{r+s}{nr}}^n\). We prove this conjecture when \(s=2\).
Given integers \(m \geq 2, r \geq 2\), let \(q_m(n), q_0^{(m)}(n), b_r^{(m)}(n)\) denote respectively the number of \(m\)-colored partitions of \(n\) into: distinct parts, distinct odd parts, and parts not divisible by \(r\).We obtain recurrences for each of the above-mentioned types of partition functions.
A reflection of a regular map on a Riemann surface fixes some simple closed curves, which are called \({mirrors}\). Each mirror passes through some of the geometric points (vertices, face-centers and edge-centers) of the map such that these points form a periodic sequence which we call the \({pattern}\) of the mirror. For every mirror there exist two particular conformal automorphisms of the map that fix the mirror setwise and rotate it in opposite directions. We call these automorphisms the \({rotary\; automorphisms}\) of the mirror. In this paper, we first introduce the notion of pattern and then describe the patterns of mirrors on surfaces. We also determine the rotary automorphisms of mirrors. Finally, we give some necessary conditions under which all reflections of a regular map are conjugate.
We prove the non-existence of maximal partial spreads of size \(76\) in \(\text{PG}(3,9)\). Relying on the classification of the minimal blocking sets of size 15 in \(\text{PG}(2,9)\) \([22]\), we show that there are only two possibilities for the set of holes of such a maximal partial spread. The weight argument of Blokhuis and Metsch \([3]\) then shows that these sets cannot be the set of holes of a maximal partial spread of size \(76\). In \([17]\), the non-existence of maximal partial spreads of size \(75\) in \(\text{PG}(3,9)\) is proven. This altogether proves that the largest maximal partial spreads, different from a spread, in \(\text{PG}(3,q = 9)\) have size \(q^2 – q + 2 = 74\).
A weakly connected dominating set \(W\) of a graph \(G\) is a dominating set such that the subgraph consisting of \(V(G)\) and all edges incident on vertices in \(W\) is connected. In this paper, we generalize it to \([r, R]\)-dominating set which means a distance \(r\)-dominating set that can be connected by adding paths with length within \(R\). We present an algorithm for finding \([r, R]\)-dominating set with performance ratio not exceeding \(ln \Delta_r + \lceil \frac{2r+1}{R}\rceil – 1\), where \(\Delta_r\) is the maximum number of vertices that are at distance at most \(r\) from a vertex in the graph. The bound for size of minimum \([r, R]\)-dominating set is also obtained.
For \(n \in \mathbb{N}\), let \(a_n\) count the number of ternary strings of length \(n\) that contain no consecutive \(1\)s. We find that \(a_n = \left(\frac{1}{2}+\frac{\sqrt{3}}{3}\right)\left(1 + \sqrt{3}\right)^n – \left(\frac{1}{2}-\frac{\sqrt{3}}{3}\right)\left(1 – \sqrt{3}\right)^n\). For a given \(n \geq 0\), we then determine the following for these \(a_n\) ternary strings:
(1)the number of \(0’\)s, \(1’\)s, and \(2’\)s;(2)the number of runs;(3) the number of rises, levels, and descents; and
(4)the sum obtained when these strings are considered as base \(3\) integers.
Following this, we consider the special case for those ternary strings (among the \(a_n\) strings we first considered) that are palindromes, and determine formulas comparable to those in (1) – (4) above for this special case.
Topological indices of nanotubes are numerical descriptors that are derived from the graph of chemical compounds. Such indices, based on the distances in the graph, are widely used for establishing relationships between the structure of nanotubes and their physico-chemical properties. The Szeged index is obtained as a bond additive quantity, where bond contributions are given as the product of the number of atoms closer to each of the two end points of each bond. In this paper, we find an exact expression for the Szeged index of an armchair polyhex nanotube \((TUAC_6{[p,k]}\)).
It is widely recognized that certain graph-theoretic extremal questions play a major role in the study of communication network vulnerability. These extremal problems are special cases of questions concerning the realizability of graph invariants. We define a CS(\(p, q, \lambda, \delta\)) graph as a connected, separable graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). In this notation, if the “CS” is omitted the graph is not necessarily connected and separable. An arbitrary quadruple of integers \((a, b, c, d)\) is called CS(\(p, q, A, 5\)) realizable if there is a CS(\(p, q, \lambda, \delta\)) graph with \(p = a, q = b, \lambda = c\) and \(\delta= d\). Necessary and sufficient conditions for a quadruple to be CS(\(p, q,\lambda, \delta\)) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta), (p, q, \lambda, \Delta), (p, q, \delta, \Delta), (p, q, \lambda, \delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(A\) denotes the maximum degree for all points in a graph and \(\lambda\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa), (p, q, \lambda), (p, q, \delta), (p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.
We use \(k\)-trees to generalize the sequence of Motzkin numbers and show that Baxter’s generalization of Temperley-Lieb operators is a special case of our generalization of Motzkin numbers. We also obtain a recursive summation formula for the terms of \(3\)-Motzkin numbers and investigate some asymptotic properties of the terms of \(k\)-Motzkin numbers.
In this article, defining the matrix extensions of the Fibonacci and Lucas numbers, we start a new approach to derive formulas for some integer numbers which have appeared, often surprisingly, as answers to intricate problems, in conventional and in recreational Mathematics. Our approach provides a new way of looking at integer sequences from the perspective of matrix algebra, showing how several of these integer sequences relate to each other.
For a finite group \(G\) the commutativity degree,
\[d(G)=\frac{|\{(x,y)|x,y \in G, xy=yx\}|}{|G|^2}\]
is defined and studied by several authors and when \(d(G) \geq \frac{1}{2}\) it is proved by P. Lescot in 1995 that \(G\) is abelian , or \(\frac{G}{Z(G)}\) is elementary abelian with \(|G’| = 2\), or \(G\) is isoclinic with \(S_3\) and \(d(G) = 1\). The case when \(d(G) < \frac{1}{2}\) is of interest to study. In this paper we study certain infinite classes of finite groups and give explicit formulas for \(d(G)\). In some cases the groups satisfy \(\frac{1}{4} < d(G) < \frac{1}{2}\). Some of the groups under study are nilpotent of high nilpotency classes.
In this paper, we construct a new infinite family of balanced binary sequences of length \(N = 4p\), \(p \equiv 5 \pmod{8}\) with optimal autocorrelation magnitude \(\{N, 0, \pm 4\}\).
The cocircuits of a splitting matroid \(M_{i,j}\) are described in terms of the cocircuits of the original matroid \(M\).
Let \(G\) be a graph with vertex set \(V(G)\) and let \(f\) be a nonnegative integer-valued function defined on \(V(G)\). A spanning subgraph \(F\) of \(G\) is called an \(f\)-factor if \(d_F(x) = f(x)\) for every \(x \in V(F)\). In this paper, we present some sufficient conditions for the existence of \(f\)-factors and connected \((f-2, f)\)-factors in \(K_{1,n}\)-free graphs. The conditions involve the minimum degree, the stability number, and the connectivity of graph \(G\).
We classify the minimal blocking sets of size 15 in \(\mathrm{PG}(2,9)\). We show that the only examples are the projective triangle and the sporadic example arising from the secants to the unique complete 6-arc in \(\mathrm{PG}(2,9)\). This classification was used to solve the open problem of the existence of maximal partial spreads of size 76 in \(\mathrm{PG}(3,9)\). No such maximal partial spreads exist \([13]\). In \([14]\), also the non-existence of maximal partial spreads of size 75 in \(\mathrm{PG}(3,9)\) has been proven. So, the result presented here contributes to the proof that the largest maximal partial spreads in \(\mathrm{PG}(3,q=9)\) have size \(q^2-q+2=74\).
Our work in this paper is concerned with a new kind of fuzzy ideal of a \(K\)-algebra called an \((\in, \in \vee_q)\)-fuzzy ideal. We investigate some interesting properties of \((\in, \in \vee_q)\)-fuzzy ideals of \(K\)-algebras. We study fuzzy ideals with thresholds which is a generalization of both fuzzy ideals and \((\in, \in \vee_q)\)-fuzzy ideals. We also present characterization theorems of implication-based fuzzy ideals.
Let \(G\) be a digraph. For two vertices \(u\) and \(v\) in \(G\), the distance \(d(u,v)\) from \(u\) to \(v\) in \(G\) is the length of the shortest directed path from \(u\) to \(v\). The eccentricity \(e(v)\) of \(v\) is the maximum distance of \(v\) to any other vertex of \(G\). A vertex \(u\) is an eccentric vertex of \(v\) if the distance from \(v\) to \(u\) is equal to the eccentricity of \(v\). The eccentric digraph \(ED(G)\) of \(G\) is the digraph that has the same vertex set as \(G\) and the arc set defined by: there is an arc from \(u\) to \(v\) if and only if \(v\) is an eccentric vertex of \(u\). In this paper, we determine the eccentric digraphs of digraphs for various families of digraphs and we get some new results on the eccentric digraphs of the digraphs.
We present \(3\) open challenges in the field of Costas arrays. They are: a) the determination of the number of dots on the main diagonal of a Welch array, and especially the maximal such number for a Welch array of a given order; b) the conjecture that the fraction of Welch arrays without dots on the main diagonal behaves asymptotically as the fraction of permutations without fixed points and hence approaches \(1/e\) and c) the determination of the parity populations of Golomb arrays generated in fields of characteristic \(2\).
Let \(G\) be the graph obtained from \(K_{3,3}\) by deleting an edge. We find a list assignment with \(|L(v)| = 2\) for each vertex \(v\) of \(G\), such that \(G\) is uniquely \(L\)-colorable, and show that for any list assignment \(L’\) of \(G\), if \(|Z'(v)| \geq 2\) for all \(v \in V(G)\) and there exists a vertex \(v_0\) with \(|L'(v_0)| > 2\), then \(G\) is not uniquely \(L’\)-colorable. However, \(G\) is not \(2\)-choosable. This disproves a conjecture of Akbari, Mirrokni, and Sadjad (Problem \(404\) in Discrete Math. \(266(2003) 441-451)\).
A total dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set. In this note, we show that the vertex set of every graph with minimum degree at least two and with no component that is a \(5\)-cycle can be partitioned into a dominating set and a total dominating set.
Let \(G\) be an undirected graph, \(A\) be an (additive) Abelian group and \(A^* = A – \{0\}\). A graph \(G\) is \(A\)-connected if \(G\) has an orientation such that for every function \(b: V(G) \longmapsto A\) satisfying \(\sum_{v\in V(G)} b(v) = 0\), there is a function \(f: E(G) \longmapsto A^*\) such that at each vertex \(v\in V(G)\) the net flow out of \(v\) equals \(b(v)\). We investigate the group connectivity number \(\Lambda_g(G) = \min\{n; G \text{ is } A\text{-connected for every Abelian group with } |A| \geq n\}\) for complete bipartite graphs, chordal graphs, and biwheels.
Various enumeration problems for classes of simply generated families of trees have been the object of investigation in the past. We mention the enumeration of independent subsets, connected subsets or matchings for instance. The aim of this paper is to show how combinatorial problems of this type can also be solved for rooted trees and trees, which enables us to take better account of isomorphisms. As an example, we will determine the average number of independent vertex subsets of trees and binary rooted trees (every node has outdegree \(\leq 2\)).
In this paper, first we introduce the concept of a \({connected}\) graph homomorphism as a homomorphism for which the inverse image of any edge is either empty or a connected graph, and then we concentrate on chromatically connected (resp. chromatically disconnected) graphs such as \(G\) for which any \(\chi(G)\)-colouring is a connected (resp. disconnected) homomorphism to \(K_{\chi(G)}\).
In this regard, we consider the relationships of the new concept to some other notions as uniquely-colourability. Also, we specify some classes of chromatically disconnected graphs such as Kneser graphs \(KG(m,n)\) for which \(m\) is sufficiently larger than \(n\), and the line graphs of non-complete class II graphs.
Moreover, we prove that the existence problem for connected homomorphisms to any fixed complete graph is an NP-complete problem.
We show that every \(2\)-connected cubic graph of order \(n > 8\) admits a \(P_3\)-packing of at least \(\frac{9n}{11}n\) vertices. The proof is constructive, implying an \(O(M(n))\) time algorithm for constructing such a packing, where \(M(n)\) is the time complexity of the perfect matching problem for \(2\)-connected cubic graphs.
The locally twisted cube \(LTQ_n\) is a newly introduced interconnection network for parallel computing. As a variant of the hypercube \(Q_n\), \(LTQ_n\) has better properties than \(Q_n\) with the same number of links and processors. Yang, Megson and Evans Evans [Locally twisted cubes are \(4\)-pancyclic, Applied Mathematics Letters, \(17 (2004), 919-925]\) showed that \(LTQ_n\) contains a cycle of every length from \(4\) to \(2^n\). In this note, we improve this result by showing that every edge of \(LTQ_n\) lies on a cycle of every length from \(4\) to \(2^n\) inclusive.
Necessary and sufficient conditions are given for the existence of a \((K_3 + e, \lambda)\)-group divisible design of type \(g^tu^1\).
A \(\lambda\)-design on \(v\) points is a set of \(v\) subsets (blocks) of a \(v\)-set such that any two distinct blocks meet in exactly \(\lambda\) points and not all of the blocks have the same size. Ryser’s and Woodall’s \(\lambda\)-design conjecture states that all \(4\)-designs can be obtained from symmetric designs by a complementation procedure. In this paper, we establish feasibility criteria for the existence of \(\lambda\)-designs with two block sizes in the form of integrality conditions, equations, inequalities, and Diophantine equations involving various parameters of the designs. We use these criteria and a computer to prove that the \(\lambda\)-design conjecture is true for all \(\lambda\)-designs with two block sizes with \(v \leq 90\) and \(\lambda \neq 45\).
In this paper, we consider the relationships between the sums of the Fibonacci and Lucas numbers and \(1\)-factors of bipartite graphs.
We define extended orthogonal sets of \(d\)-cubes and show that they are equivalent to a class of orthogonal arrays, to geometric nets and a class of codes. As a corollary, an upper bound for the maximal number of \(d\)-cubes in an orthogonal set is obtained.
For two given graphs \(G_1\) and \(G_2\), the \({Ramsey\; number}\) \(R(G_1, G_2)\) is the smallest integer \(n\) such that for any graph \(G\) of order \(n\), either \(G\) contains \(G_1\) or the complement of \(G\) contains \(G_2\). Let \(P_n\) denote a path of order \(n\) and \(W_{m}\) a wheel of order \(m+1\). Chen et al. determined all values of \(R(P_n, W_{m})\) for \(n \geq m-1\). In this paper, we establish the best possible upper bound and determine some exact values for \(R(P_n, W_{m})\) with \(n \leq m-2\).
A container \(C(x,y)\) is a set of vertex-disjoint paths between vertices \(z\) and \(y\) in a graph \(G\). The width \(w(C(x,y))\) and length \(L(C(x,y))\) are defined to be \(|C(x,y)|\) and the length of the longest path in \(C(x,y)\) respectively. The \(w\)-wide distance \(d_w(x,y)\) between \(x\) and \(y\) is the minimum of \(L(C(x,y))\) for all containers \(C(x,y)\) with width \(w\). The \(w\)-wide diameter \(d_w(G)\) of \(G\) is the maximum of \(d_w(x,y)\) among all pairs of vertices \(x,y\) in \(G\), \(x \neq y\). In this paper, we investigate some problems on the relations between \(d_w(G)\) and diameter \(d(G)\) which were raised by D.F. Hsu \([1]\). Some results about graph equation of \(d_w(G)\) are proved.
Greedy defining sets have been studied for the first time by the author for graphs. In this paper, we consider greedy defining sets for Latin squares and study the structure of these sets in Latin squares. We give a general bound for greedy defining numbers and linear bounds for greedy defining numbers of some infinite families of Latin squares. Greedy defining sets of circulant Latin squares are also discussed in the paper.
Let \(C_n^{(t)}\) denote the cycle with \(n\) vertices, and \(C_n^{(t)}\) denote the graphs consisting of \(t\) copies of \(C_n\), with a vertex in common. Koh et al. conjectured that \(C_n^{(t)}\) is graceful if and only if \(nt \equiv 0, 3 \pmod{4}\). The conjecture has been shown true for \(n = 3, 5, 6, 7, 9, 4k\). In this paper, the conjecture is shown to be true for \(n = 11\).
Let \(P(G; \lambda)\) denote the chromatic polynomial of a graph \(G\), expressed in the variable \(\lambda\). Then \(G\) is said to be chromatically unique if \(G\) is isomorphic with \(H\) for any graph \(H\) such that \(P(H; \lambda) = P(G; \lambda)\). The graph consisting of \(s\) edge-disjoint paths joining two vertices is called an \(s\)-bridge graph. In this paper, we provide a new family of chromatically unique \(5\)-bridge graphs.
Recently in \([5]\), the author considered certain reciprocal sums of general second order recurrence \(\{W_n\}\). In this paper, we generalize the results of Xi and we give some new results for the reciprocal sums of \(k\)-th power of general second order recurrence \(\{W_{kn}\}\) for arbitrary positive integer \(k\).
In this article, we study the generalized Bernoulli and Euler polynomials, and obtain relationships between them, based upon the technique of matrix representation.
Let \(K_v\) be the complete graph with \(v\) vertices. Let \(G\) be a finite simple graph. A \(G\)-decomposition of \(K_v\), denoted by \(G\)-GD\((v)\), is a pair \((X, \mathcal{B})\) where \(X\) is the vertex set of \(K_v\), and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in exactly one block of \(\mathcal{B}\). In this paper, nine graphs \(G_i\) with six vertices and nine edges are discussed, and the existence of \(G_i\)-decompositions are completely solved, \(1 \leq i \leq 9\).
A graph \(G\) is called \({uniquely\; k-list \;colorable}\), or \(UkLC\) for short, if it admits a \(k\)-list assignment \(L\) such that \(G\) has a unique \(L\)-coloring. A graph \(G\) is said to have the property \(M(k)\) (M for Marshal Hall) if and only if it is not \(UkLC\). In \(1999\), M. Ghebleh and E.S. Mahmoodian characterized the \(U3LC\) graphs for complete multipartite graphs except for nine graphs. At the same time, for the nine exempted graphs, they give an open problem: verify the property \(M(3)\) for the graphs \(K_{2,2,\ldots,2}\) for \(r = 4,5,\ldots,8\), \(K_{2,3,4}\), \(K_{1*4,4}\), \(K_{1*4,4}\), and \(K_{1*5,4}\). Until now, except for \(K_{1*5,4}\), the other eight graphs have been showed to have the property \(M(3)\) by W. He et al. In this paper, we show that graph \(K_{1*5,4}\) has the property \(M(3)\), and as consequences, \(K_{1*4,4}\), \(K_{2,2,4}\) have the property \(M(3)\). Therefore the \(U3LC\) complete multipartite graphs are completely characterized.
Given a graph \(G\), we say \(S \subseteq V(G)\) is \({resolving}\) if for each pair of distinct \(u, v \in V(G)\) there is a vertex \(x \in S\) where \(d(u, x) \neq d(v, x)\). The metric dimension of \(G\) is the minimum cardinality of all resolving sets. For \(w \in V(G)\), the distance from \(w\) to \(S\), denoted \(d(w, S)\), is the minimum distance between \(w\) and the vertices of \(S\). Given \(\mathcal{P} = \{P_1, P_2, \ldots, P_k\}\) an ordered partition of \(V(G)\), we say \(P\) is resolving if for each pair of distinct \(u, v \in V(G)\) there is a part \(P_i\) where \(d(u, P_i) \neq d(v, P_i)\). The partition dimension is the minimum order of all resolving partitions. In this paper, we consider relationships between metric dimension, partition dimension, diameter, and other graph parameters. We construct “universal examples” of graphs with given partition dimension, and we use these to provide bounds on various graph parameters based on metric and partition dimensions. We form a construction showing that for all integers \(a\) and \(b\) with \(3 \leq a \leq \beta + 1\), there exists a graph \(G\) with partition dimension \(\alpha\) and metric dimension \(\beta\), answering a question of Chartrand, Salehi, and Zhang \([3]\).
The total chromatic number \(\chi_\tau(G)\) is the least number of colours needed to colour the vertices and edges of a graph \(G\) such that no incident or adjacent elements (vertices or edges) receive the same colour. This work determines the total chromatic number of grids, particular cases of partial grids, near-ladders, and of \(k\)-dimensional cubes.
The \({star arboricity}\) \(sa(G)\) of a graph \(G\) is the minimum number of star forests which are needed to decompose all edges of \(G\). For integers \(k\) and \(n\), \(1 \leq k \leq n\), the \({crown}\) \(C_{n,k}\) is the graph with vertex set \(\{a_0, a_1, \ldots, a_{n-1}, b_0, b_1, \ldots, b_{n-1}\}\) and edge set \(\{a_ib_j : i = 0, 1, \ldots, n-1, j \equiv i+1, i+2, \ldots, i+k \pmod{n}\}\). In \([2]\), Lin et al. conjectured that for every \(k\) and \(n\), \(3 \leq k \leq n-1\), the star arboricity of the crown \(C_{n,k}\) is \(\lceil k/2 \rceil + 1\) if \(k\) is odd and \(\lceil k/2 \rceil + 2\) otherwise. In this note, we show that the above conjecture is not true for the case \(n = 9t\) (\(t\) is a positive integer) and \(k = 4\) by showing that \(sa(C_{9t,4}) = 3\).
Let \(\mathcal{P}(n,k)\) denote the number of graphs on \(n+k\) vertices that contain \(P_n\), a path on \(n\) vertices, as an induced subgraph. In this note, we will find upper and lower bounds for \(\mathcal{P}(n,k)\). Using these bounds, we show that for \(k\) fixed, \(\mathcal{P}(n,k)\) behaves roughly like an exponential function of \(n\) as \(n\) gets large.
A \({dominating \;broadcast}\) of a graph \(G\) of diameter \(d\) is a function \(f: V(G) \to \{0, 1, 2, \ldots, d\}\) such that for all \(v \in V(G)\) there exists \(u \in V(G)\) with \(d(u, v) \leq f(u)\). We investigate dominating broadcasts for caterpillars.
In this paper, we obtain a fundamental result on the dynamical behavior of symmetric weighted mappings for two-dimensional real sequence spaces \({R}_s\).
In \(2006\), Mojdeh and Jafari Rad [On the total domination critical graphs, Electronic Notes in Discrete Mathematics, 24 (2006), 89-92] gave an open problem: Does there exist a \(3\)-\(\gamma_t\)-critical graph \(G\) of order \(\Delta(G) + 3\) with \(\Delta(G)\) odd and \(\delta(G) \geq 2\)? In this paper, we positively answer that for each odd integer \(n \geq 9\), there exists a \(3\)-\(\gamma_t\)-critical graph \(G_n\) of order \(n+3\) with \(\delta(G) \geq 2\). On the contrary, we also prove that for \(\Delta(G) = 3, 5, 7\), there is no \(3\)-\(\gamma_t\)-critical graph of order \(\Delta(G) + 3\) with \(\delta(G) \geq 2\).
Let \(\{w_n\}\) be a second-order recurrence sequence. According to the definition and characteristics of the recurrent sequence, we proved a recursion formula for certain reciprocal sums whose denominators are products of consecutive elements of \(\{w_n\}\).
Let \(G\) be a graph in which each vertex has been colored using one of \(k\) colors, say \(c_1, c_2, \ldots, c_k\). If an \(m\)-cycle \(C\) in \(G\) has \(n_i\) vertices colored \(c_i\), \(i = 1, 2, \ldots, k\), and \(|n_i – n_j| \leq 1\) for any \(i, j \in \{1, 2, \ldots, k\}\), then \(C\) is equitably \(k\)-colored. An \(m\)-cycle decomposition \(\mathcal{C}\) of a graph \(G\) is equitably \(k\)-colorable if the vertices of \(G\) can be colored so that every \(m\)-cycle in \(\mathcal{C}\) is equitably \(k\)-colored. For \(m = 4, 5\), and \(6\), we completely settle the existence problem for equitably \(2\)-colorable \(m\)-cycle decompositions of complete graphs with the edges of a \(1\)-factor added.
Suppose a network facility location problem is modelled by means of an undirected, simple graph \(G = (\mathcal{V, E})\) with \(\mathcal = \{v_1, \ldots, v_n\}\). Let \(\mathbf{r} = (r_1, \ldots, r_n)\) and \(\mathbf{s} = (s_1, \ldots, s_n)\) be vectors of nonnegative integers and consider the combinatorial optimization problem of locating the minimum number, \(\gamma(\mathbf{r}, \mathbf{s}, G)\) (say), of commodities on the vertices of \(G\) such that at least \(s_j\) commodities are located in the vicinity of (i.e. in the closed neighbourhood of) vertex \(v_j\), with no more than \(r_j\) commodities placed at vertex \(v_j\) itself, for all \(j = 1, \ldots, n\). In this paper we establish lower and upper bounds on the parameter \(\gamma(\mathbf{r}, \mathbf{s}, G)\) for a general graph \(G\). We also determine this parameter exactly for certain classes of graphs, such as paths, cycles, complete graphs, complete bipartite graphs and establish good upper bounds on \(\gamma(\mathbf{r}, \mathbf{s}, G)\) for a class of grid graphs in the special case where \(r_j = r\) and \(s_j = s\) for all \(j = 1, \ldots, n\).
Let \(A\) be an arbitrary circulant stochastic matrix, and let \(\underline{x}_0\) be a vector. An “asymptotic” canonical form is derived for \(A^k\) (as \(k \to \infty\)) as a tensor product of three simple matrices by employing a pseudo-invariant on sections of states for a Markov process with transition matrix \(A\), and by analyzing how \(A\) acts on the sections, through its auxiliary polynomial. An element-wise asymptotic characterization of \(A^k\) is also given, generalizing previous results to cover both periodic and aperiodic cases. For a particular circulant stochastic matrix, identifying the intermediate stage at which fractions first appear in the sequence \(\underline{x}_k = A^k \underline{x}_0\), is accomplished by utilizing congruential matrix identities and \((0,1)\)-matrices to determine the minimum \(2\)-adic order of the coordinates of \(\underline{x}_k\), through their binary expansions. Throughout, results are interpreted in the context of an arbitrary weighted average repeatedly applied simultaneously to each term of a finite sequence when read cyclically.
A graph \(G\) is \(s\)-Hamiltonian if for any \(S \subseteq V(G)\) of order at most \(s\), \(G-S\) has a Hamiltonian cycle, and \(s\)-Hamiltonian connected if for any \(S \subseteq V(G)\) of order at most \(s\), \(G-S\) is Hamiltonian-connected. Let \(k > 0, s \geq 0\) be two integers. The following are proved in this paper:(1) Let \(k \geq s+2\) and \(s \leq n-3\). If \(G\) is a \(k\)-connected graph of order \(n\) and if \(\max\{d(v) : v \in I\} \geq (n+s)/2\) for every independent set \(I\) of order \(k-s\) such that \(I\) has two distinct vertices \(x,y\) with \(1 \leq |N(x) \cap N(y)| \leq \alpha(G)+s-1\), then \(G\) is \(s\)-Hamiltonian.(2) Let \(k \geq s+3\) and \(s \leq n-2\). If \(G\) is a \(k\)-connected graph of order \(n\) and if \(\max\{d(v) : v \in I\} \geq (n+s+1)/2\) for every independent set \(I\) of order \(k-s-1\) such that \(I\) has two distinct vertices \(x,y\) with \(1 \leq |N(x) \cap N(y)| \leq \alpha(G)+s\), then \(G\) is \(s\)-Hamiltonian connected.These results extend several former results by Dirac, Ore, Fan, and Chen.
We show that every generalized quadrangle of order \((4,6)\) with a spread of symmetry is isomorphic to the Ahrens-Szekeres generalized quadrangle \(\text{AS}(5)\). It then easily follows that every generalized quadrangle of order \(5\) with an axis of symmetry is isomorphic to the classical generalized quadrangle \(\text{Q}(4, 5)\).
A \(C_5C_7\) net is a trivalent decoration made by alternating pentagons \(C_5\) and heptagons \(C_7\). It can cover either a cylinder or a torus. In this paper, we compute the Szeged index of \(HC_5C_7[ r, p ]\) nanotube.
We present algebraic constructions yielding incidence matrices for all finite Desarguesian elliptic semiplanes of types \(C, D\), and \(L\). Both basic ingredients and suitable notations are derived from addition and multiplication tables of finite fields. This approach applies also to the only elliptic semiplane of type B known so far. In particular, the constructions provide intrinsic tactical decompositions and partitions for these elliptic semiplanes into elliptic semiplanes of smaller order.
The number of essentially different square polyominoes of order \(n\) and minimum perimeter \(p(n)\) is enumerated.
Let \(G = (V, E)\) be a graph. Then \(S \subseteq V\) is an excess-\(t\) global powerful alliance if \(|N[v] \cap S| \geq |N[v] \cap (V – S)| + t\) for every \(v \in V\). If \(t = 0\), this definition reduces to that of a \({global \;powerful \;alliance}\). Here we determine bounds on the cardinalities of such sets \(S\).
A total perfect code in a graph is a subset of the graph’s vertices with the property that each vertex in the graph is adjacent to exactly one vertex in the subset. We prove that the tensor product of any number of simple graphs has a total perfect code if and only if each factor has a total perfect code.
We calculate the norm of weighted composition operators \(uC_\psi\) from the Bloch space to the weighted space \(H^\infty_\mu({B})\) on the unit ball \({B}\).
Let \(P\) be a polygon whose vertices have been colored (labeled) cyclically with the numbers \(1, 2, \ldots, c\). Motivated by conjectures of Propp, we are led to consider partitions of \(P\) into \(k\)-gons which are proper in the sense that each \(k\)-gon contains all \(c\) colors on its vertices. Counting the number of proper partitions involves a generalization of the \(k\)-Catalan numbers. We also show that in certain cases, any proper partition can be obtained from another by a sequence of moves called flips.
Let \(n, k\) be integers and \(k < n\). Denote by \(\mathcal{G}_{n,k}\) and \(\mathcal{G}'_{n,k}\) the set of graphs of order \(n\) with \(k\) independent vertices and the set of graphs of order \(n\) with \(k\) independent edges, respectively. The bounds of the spectral radius of graphs in \(\mathcal{G}_{n,k}\) and \(\mathcal{G}'_{n,k}\) are obtained.
Let \(n \in \mathbb{N}\) and let \(A \subseteq \mathbb{Z}_n\) be such that \(A\) does not contain \(0\) and is non-empty. We define \({E}_A(n)\) to be the least \(t \in \mathbb{N}\) such that for all sequences \((x_1, \ldots, x_t) \in \mathbb{Z}^t\), there exist indices \(j_1, \ldots, j_n \in \mathbb{N}\), \(1 \leq j_1 < \cdots < j_n \leq t\), and \((\theta_1, \ldots, \theta_n) \in A^n\) with \(\sum_{i=1}^n \theta_i x_{j_i} \equiv 0 \pmod{n}\). Similarly, for any such set \(A\), we define the \({Davenport Constant}\) of \(\mathbb{Z}_n\) with weight \(A\) denoted by \(D_A(n)\) to be the least natural number \(k\) such that for any sequence \((x_1, \ldots, x_k) \in \mathbb{Z}^k\), there exist a non-empty subsequence \((x_{j}, \ldots, x_{j_i})\) and \((a_1, \ldots, a_l) \in A^t\) such that \(\sum_{i=1}^n a_i x_{j_i} \equiv 0 \pmod{n}\). Das Adhikari and Rath conjectured that for any set \(A \subseteq \mathbb{Z}_n \setminus \{0\}\), the equality \({E}_A(n) = D_A(n) + n – 1\) holds. In this note, we determine some Davenport constants with weights and also prove that the conjecture holds in some special cases.
In this paper, we introduce an extension of the hyperbolic Fibonacci and Lucas functions which were studied by Stakhov and Rozin. Namely, we define hyperbolic functions by second-order recurrence sequences and study their hyperbolic and recurrence properties. We give the corollaries for Fibonacci, Lucas, Pell, and Pell-Lucas numbers. We finalize with the introduction of some surfaces (the Metallic Shofars) that relate to the hyperbolic functions with the second-order recurrence sequences.
The graph’s irregularity is the sum of the absolute values of the differences of degrees of pairs of adjacent vertices in the graph. We provide various upper bounds for the irregularity of a graph, especially for \(K_{r+1}\)-free graphs, where \(K_{r+1}\) is a complete graph on \(r+1\) vertices, and trees and unicyclic graphs of given number of pendant vertices.
Let \(\mathbb{F}_q^(n)\) (resp. \({AG}(n,\mathbb{F}_q)\)) be the \(n\)-dimensional vector (resp. affine) space over the finite field \(\mathbb{F}_q\). For \(1 \leq i \leq i+s \leq n-1\) (resp. \(0 \leq i \leq i+s \leq n-1\)), let \(\mathcal{L}(i,i+s;n)\) (resp. \(\mathcal{L}'(i,i+s;n)\)) denote the set of all subspaces (resp. flats) in \(\mathbb{F}_q^(n)\) (resp. \({AG}(n,\mathbb{F}_q)\)) with dimensions between \(i\) and \(i+s\) including \(\mathbb{F}_q^(n)\) and \(\{0\}\) (resp. \(\emptyset\)). By ordering \(\mathcal{L}(i,i+s;n)\) (resp. \(\mathcal{L}'(i,i+s;n)\)) by ordinary inclusion or reverse inclusion, two classes of lattices are obtained. This article discusses their geometricity.
In this paper, we give some relations involving the usual Fibonacci and generalized order-\(k\) Pell numbers. These relations show that the generalized order-\(k\) Pell numbers can be expressed as the summation of the usual Fibonacci numbers. We find families of Hessenberg matrices such that the permanents of these matrices are the usual Fibonacci numbers, \(F_{2i-1}\), and their sums. Also, extending these matrix representations, we find families of super-diagonal matrices such that the permanents of these matrices are the generalized order-\(k\) Pell numbers and their sums.
Let \(G\) be a finite group and \(S\) be a subset (possibly containing the identity element) of \(G\). We define the Bi-Cayley graph \(X = BC(G, S)\) to be the bipartite graph with vertices \(G \times \{0, 1\}\) and edges \(\{(g, 0), (sg, 1) : g \in G, s \in S\}\). In this paper, we show that if \(X = BC(G, S)\) is connected, then \(\kappa(X) = \delta(X)\).
Some new characterizations for harmonic Bergman space on the unit ball \({B}\) in \(\mathbb{R}^n\) are given in this paper. They can be described as derivative-free characterizations.
The planar Ramsey number \(PR(H_1, H_2)\) is the smallest integer \(n\) such that any planar graph on \(n\) vertices contains a copy of \(H_1\) or its complement contains a copy of \(H_2\). It is known that the Ramsey number \(R(K_4 – e, K_k – e)\) for \(k \leq 6\). In this paper, we prove that \(PR(K_4 – e, K_6 – e) = 16\) and show the lower bounds on \(PR(K_4 – e, K_k – e)\).
Let \(K_v\) be a complete graph with \(v\) vertices, and \(G = (V(G), E(G))\) be a finite simple graph. A \(G\)-design \(G-GD_\lambda(v)\) is a pair \((X, \mathcal{B})\), where \(X\) is the vertex set of \(K_v\), and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in exactly \(\lambda\) blocks of \(\mathcal{B}\). In this paper, the existence of graph designs \(G-GD_\lambda(v)\), \(\lambda > 1\), for eight graphs \(G\) with six vertices and eight edges is completely solved.
A \({weighted \;graph}\) is one in which every edge \(e\) is assigned a nonnegative number \(w(e)\), called the \({weight}\) of \(e\). The \({weight\; of \;a \;cycle}\) is defined as the sum of the weights of its edges. The \({weighted \;degree}\) of a vertex is the sum of the weights of the edges incident with it. In this paper, motivated by a recent result of Fujisawa, we prove that a \(2\)-connected weighted graph \(G\) contains either a Hamilton cycle or a cycle of weight at least \(2m/3\) if it satisfies the following conditions:
\((1)\) The weighted degree sum of every three pairwise nonadjacent vertices is at least \(m\);\((2)\)In each induced claw and each induced modified claw of \(G\), all edges have the same weight.This extends a theorem of Zhang, Broersma and Li.
The \({restricted edge-connectivity}\) of a graph is an important parameter to measure fault-tolerance of interconnection networks. This paper determines that the restricted edge-connectivity of the de Bruijn digraph \(B(d,n)\) is equal to \(2d – 2\) for \(d \geq 2\) and \(n \geq 2\) except \(B(2,2)\). As consequences, the super edge-connectedness of \(B(d,n)\) is obtained immediately.
An edge coloring of a graph is called \({square-free}\) if the sequence of colors on certain walks is not a square, that is not of the form \(x_1, \ldots, x_m, x_{1}, \ldots, x_m\) for any \(m \in \mathbb{N}\). Recently, various classes of walks have been suggested to be considered in the above definition. We construct graphs, for which the minimum number of colors needed for a square-free coloring is different if the considered set of walks vary, solving a problem posed by Brešar and Klavžar. We also prove the following: if an edge coloring of \(G\) is not square-free (even in the most general sense), then the length of the shortest square walk is at most \(8|E(G)|^2\). Hence, the necessary number of colors for a square-free coloring is algorithmically computable.
If \(x\) is a vertex of a digraph \(D\), then we denote by \(d^+ (x)\) and \(d^- (x)\) the outdegree and the indegree of \(x\), respectively. The global irregularity of a digraph \(D\) is defined by \(i_g(D) = \max\{d^+ (x),d^- (x)\} – \min\{d^+ (y), d^- (y)\}\) over all vertices \(x\) and \(y\) of \(D\) (including \(x = y\)).
A \(c\)-partite tournament is an orientation of a complete \(c\)-partite graph. Recently, Volkmann and Winzen \([9]\) proved that \(c\)-partite tournaments with \(i_g(D) = 1\) and \(c \geq 3\) or \(i_g(D) = 2\) and \(c \geq 5\) contain a Hamiltonian path. Furthermore, they showed that these bounds are best possible.
Now, it is a natural question to generalize this problem by asking for the minimal value \(g(i,k)\) with \(i,k \geq 1\) arbitrary such that all \(c\)-partite tournaments \(D\) with \(i_g(D) \leq i\) and \(c \geq g(i,k)\) have a path covering number \(pc(D) \leq k\). In this paper, we will prove that \(4i-4k \leq g(i,k) \leq 4i-3k-1\), when \(i \geq k+2\). Especially in the case \(k = 1\), this yields that \(g(i, 1) = 4i-4\), which means that all \(c\)-partite tournaments \(D\) with the global irregularity \(i_g(D) = i\) and \(c \geq 4i-4\) contain a Hamiltonian path.
In this paper, we discuss a problem on packing a unit cube with smaller cubes, which is a generalization of one of Erdős’ favorite problems: the square-packing problem. We first give the definition of the packing function \(f_3(n)\), then give the bounds for \(f_3(n)\).
A set \(S\) of vertices in a graph \(G = (V, E)\) is a restrained dominating set of \(G\) if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V \setminus S\). The graph \(G\) is called restrained domination excellent if every vertex belongs to some minimum restrained dominating set of \(G\). We provide a characterization of restrained domination excellent trees.
In this paper, \(q\)-analogues of the Pascal matrix and the symmetric Pascal matrix are studied. It is shown that the \(q\)-Pascal matrix \(\mathcal{P}_n\) can be factorized by special matrices and the symmetric \(q\)-Pascal matrix \(\mathcal{Q}_n\) has the LDU-factorization and the Cholesky factorization. As byproducts, some \(q\)-binomial identities are produced by linear algebra. Furthermore, these matrices are generalized in one or two variables, where a short formula for all powers of \(q\)-Pascal functional matrix \(\mathcal{P}_n[x]\) is given. Finally, it is similar to Pascal functional matrix, we have the exponential form for \(q\)-Pascal functional matrix.
We view a lobster in this paper as below. A lobster with diameter at least five has a unique path \(H = x_0, x_1, \ldots, x_m\) with the property that, besides the adjacencies in \(H\), both \(x_0\) and \(x_m\) are adjacent to the centers of at least one \(K_{i,s}\), where \(s > 0\), and each \(x_i\), \(1 \leq i \leq m-1\), is at most adjacent to the centers of some \(K_{1,s}\), where \(s \geq 0\). This unique path \(H\) is called the central path of the lobster. We call \(K_{1,s}\) an even branch if \(s\) is nonzero even, an odd branch if \(s\) is odd, and a pendant branch if \(s = 0\). In this paper, we give graceful labelings to some new classes of lobsters with diameter at least five. In these lobsters, the degree of each vertex \(x_i\), \(0 \leq i \leq m-1\), is even and the degree of \(x_m\) may be odd or even, and we have one of the following features:
In this paper, an algorithm for constructing self-centered graphs from trees and two more algorithms for constructing self-centered graphs from a given connected graph \(G\), by adding edges are discussed. Motivated by this, a new graph theoretic parameter \(sc_r(G)\), the minimum number of edges added to form a self-centered graph from \(G\) is defined. Bounds for this parameter are obtained and exact values of this parameter for several classes of graphs are also obtained.
A \((k;g)\)-graph is a \(k\)-regular graph with girth \(g\). A \((k;g)\)-cage is a \((k;g)\)-graph with the least number of vertices. In this note, we show that a \((k;g)\)-cage has an \(r\)-factor of girth at least \(g\) containing or avoiding a given edge for all \(r\), \(1 \leq r \leq k-1\).
This paper deals with the problem of constructing Hamiltonian paths of optimal weights in Halin graphs. There are three versions of the Hamiltonian path: none or one or two of end-vertices are specified. We present \(O(|V|)\) algorithms for all the versions of the problem.
It is widely recognized that certain graph-theoretic extremal questions play a major role in the study of communication network vulnerability. These extremal problems are special cases of questions concerning the realizability of graph invariants. We define a CS\((p, q, \lambda, \delta)\) graph as a connected, separable graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). In this notation, if the “CS” is omitted the graph is not necessarily connected and separable. An arbitrary quadruple of integers \((a, b, c, d)\) is called CS\((p, q, \lambda, \delta)\) realizable if there is a CS\((p, q, \lambda, \delta)\) graph with \(p = a\), \(q = b\), \(\lambda = c\) and \(\delta = d\). Necessary and sufficient conditions for a quadruple to be CS\((p, q, \lambda, \delta)\) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta)\), \((p, q, \lambda,\Delta )\), \((p, q, \delta, \Delta)\), \((p, q, \lambda, \delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\kappa\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.
An incidence graph of a given graph \(G\), denoted by \(I(G)\), has its own vertex set \(V(I(G)) = \{(ve) | v \in V(G), e \in E(G) \text{ and } v \text{ is incident to } e \text{ in } G\}\) such that the pair \(((ue)(vf))\) of vertices \((ue) (vf) \in V(I(G))\) is an edge of \(I(G)\) if and only if there exists at least one case of \(u = v, e = f, uv = e\) or \(uv = f\). In this paper, we carry out a constructive definition on incidence graphs, and investigate some properties of incidence graphs and some edge-colorings on several classes of them.
The maximum possible toughness among graphs with \(n\) vertices and \(m\) edges is considered for \(m \geq \lceil n^2/4 \rceil\). We thus extend results known for \(m \geq n\lfloor n/3 \rfloor\). When \(n\) is even, all of the values are determined. When \(n\) is odd, some values are determined, and the difficulties are discussed, leaving open questions.
In this paper, we, by means of Rosa’s \(\alpha\)-labelling and \(k\)-graceful labelling, prove that generalized spiders, generalized caterpillars, and generalized path-block chains are graceful under some conditions. Some of the results are stronger than that obtained in \([4]\).
We study convexity with respect to a definition of fractional independence in a graph \(G\) that is quantified over neighbourhoods rather than edges. The graphs that admit a so-called universal maximal fractional independent set are characterized, as are all such sets. A characterization is given of the maximal fractional independent sets which cannot be obtained as a proper convex combination of two other such sets.
In this paper, we consider the relationship between the toughness and the existence of fractional \(f\)-factors. It is proved that a graph $G$ has a fractional \(f\)-factor if \(t(G) \geq \frac{b^2+b}{a}-\frac{b+1}{b}\). Furthermore, we show that the result is best possible in some sense.
It is always fascinating to see what results when seemingly different areas of mathematics overlap. This article reveals one such result; number theory and linear algebra are intertwined to yield complex factorizations of the classic Fibonacci, Pell, Jacobsthal, and Mersenne numbers. Also, in this paper we define a new matrix generalization of the Fibonacci numbers, and using essentially a matrix approach we show some properties of this matrix sequence.
The notion of meandric polygons is introduced in this paper. A bijection exists between the set of meandric polygons and that of closed meanders. We use these polygons to enumerate the set of meanders which have a fixed number of arcs of the meandric curves lying above and below the horizontal line at a given point.
In this paper, we give a sufficient and necessary condition for a \(k\)-extendable graph to be \(2k\)-factor-critical when \(k = \frac{v}{4}\), and prove some results on independence numbers in \(n\)-factor-critical graphs and \(k\frac{1}{2}\)-extendable graphs.
In this paper, we show that some families of graphs are arbitrarily graceful or almost graceful.
We consider the lattice of order ideals of the union of an \(n\)-element fence and an antichain of size \(i\), whose Hasse diagram turns out to be isomorphic to the \(i\)-th extended Fibonacci cube. We prove that the Whitney numbers of these lattices form a unimodal sequence satisfying a particular property, called \({alternating}\), we find the maximum level of the game sequence and determine the exact values of these numbers.
Let \(D\) be a strongly connected digraph with order at least two. Let \(T(D)\) denote the total digraph of \(D\), and let \(\kappa(D)\) and \(\lambda(D)\) denote the connectivity and arc-connectivity of \(D\), respectively. In this paper, we study super-arc-connected and super-connected total digraphs. The following results are obtained:
A vertex\(|\)matching-partition \((V|M)\) of a simple graph \(G\) is a spanning collection of vertices and independent edges of \(G\). Let vertex \(v \in V\) have weight \(w_v\) and edge \(e \in M\) have weight \(w_e\). Then the weight of \(V|M\) is \(w(V|M) = \prod_{v \in V} w_v + \prod_{e \in M} w_e\). Define the vertex|matching-partition function of \(G\) as \(W(G) = \sum_{V|M} w(V|M)\).
In this paper, we study this function when \(G\) is a path and a cycle. We generate all orthogonal polynomials as vertex|matching-partition functions of suitably labelled paths, and indicate how to find their derivatives in some cases. Here Taylor’s Expansion is used, and an application to associated polynomials is given. We also give a combinatorial interpretation of coefficients in the case of multiplicative and additive weights. Results are extended to the weighted cycle.
Let \(k\) be a nonnegative integer, and let \(\gamma(G)\) and \(i(G)\) denote the domination number and the independent domination number of a graph \(G\), respectively. The so-called \(i_k\)-perfect graphs consist of all such graphs \(G\) in which \(i(H) – \gamma(H) \leq k\) holds for every induced subgraph \(H\) of \(G\). This concept, introduced by I. Zverovich in \([5]\), generalizes the well-known domination perfect graphs. He conjectured that \(i\gamma (k)\)-perfect graphs also have a finite forbidden induced subgraphs characterization, as is the case for domination perfect graphs. Recently, Dohmen, Rautenbach, and Volkmann obtained such a characterization for all \(i\gamma(1)\)-perfect forests. In this paper, we characterize the \(i\gamma(1)\)-perfect graphs with girth at least six.
Let \(G\) be a simple and connected graph of order \(p \geq 2\). A \({proper k-total-coloring}\) of a graph \(G\) is a mapping \(f\) from \(V(G) \bigcup E(G)\) into \(\{1, 2, \ldots, k\}\) such that every two adjacent or incident elements of \(V(G) \bigcup E(G)\) are assigned different colors. Let \(C_f(u) = f(u) \bigcup \{f(uv) | uv \in E(G)\}\) be the \({neighbor \;color-set}\) of \(u\). If \(C_f(u) \neq C_f(v)\) for any two vertices \(u\) and \(v\) of \(V(G)\), we say \(f\) is a \({vertex-distinguishing \;proper\; k-total-coloring}\) of \(G\), or a \({k-VDT-coloring}\) of \(G\) for short. The minimal number of all \(k\)-VDT-colorings of \(G\) is denoted by \(\chi_{vt}(G)\), and it is called the \({VDTC \;chromatic \;number}\) of \(G\). For some special families of graphs, such as the complete graph \(K_n\), complete bipartite graph \(K_{m,n}\), path \(P_m\), and circle \(C_m\), etc., we determine their VDTC chromatic numbers and propose a conjecture in this article.
The cochromatic number of a graph \(G\), denoted by \(z(G)\), is the fewest number of parts we need to partition \(V(G)\) so that each part induces in \(G\) an empty or a complete graph. A graph \(G\) with \(z(G) = n\) is called \({critically n-cochromatic}\) if \(z(G – v) = n – 1\) for each vertex \(v\) of \(G\), and \({minimally n-cochromatic}\) if \(z(G – e) = n – 1\) for each edge \(e\) of \(G\).
We show that for a graph \(G\), \(K_{1} \cup G \cup K_{2} \cup \cdots \cup K_{n-1} \cup G\) is a critically \(n\)-cochromatic graph if and only if \(G\) is \(K_{n}\), \((n \geq 2)\). We consider general minimally cochromatic graphs and obtain a result that a minimally cochromatic graph is either a critically cochromatic graph or a critically cochromatic graph plus some isolated vertices. We also prove that given a graph \(G\), then \(K_{1} \cup G \cup K_{2} \cup \cdots \cup K_{n-1} \cup G\) \((n \geq 2)\) is minimally \(n\)-cochromatic if and only if \(G\) is \(K_{n}\) or \(\overline{K_{n-1}} \cup \overline{K_{p}}\) for \(p \geq 1\). We close by giving some properties of minimally \(n\)-cochromatic graphs.
We examine the inverse domination number of a graph, as well as two reasonable candidates for the fractional analogue of this parameter. We also examine the relations among these and other graph parameters. In particular, we show that both proposed fractional analogues of the inverse domination number are no greater than the fractional independence number. These results establish the fractional analogue of a well-known conjecture about the inverse domination and vertex independence numbers of a graph.
We consider a \(2\)-coloring of arcs on the primitive extremal tournament with the largest exponent on \(n\) vertices and \(m\) arcs. This \(2\)-colored digraph is a \(2\)-primitive tournament. Then we consider the \(2\)-exponent of a \(2\)-primitive tournament. In this paper, we give an upper bound for the \(2\)-exponent of the primitive extremal tournament.
Let \(G = (V(G), E(G))\) be a nonempty graph (may have parallel edges). The line graph \(L(G)\) of \(G\) is the graph with \(V(L(G)) = E(G)\), and in which two vertices \(e\) and \(e’\) are joined by an edge if and only if they have a common vertex in \(G\). We call the complement of \(L(G)\) as the jump graph. In this note, we give a simple sufficient and necessary condition for a jump graph to have a perfect matching.
We introduce a new technique for constructing pairwise balanced designs and group divisible designs from finite groups. These constructed designs do not yield designs with new parameters, but our construction gives rise to designs having a transitive automorphism group that also preserves the resolution classes.
A shell graph of order \(n\), denoted by \(H(n, n-3)\), is the graph obtained from the cycle \(C_n\) of order \(n\) by adding \(n-3\) chords incident with a common vertex, say \(u\). Let \(v\) be a vertex adjacent to \(u\) in \(C_n\). Sethuraman and Selvaraju \([3]\) conjectured that for all \(k \geq 1\) and for all \(n_i \geq 4\), \(1 \leq i \leq k\), one edge \((uv)\) union of \(k\)-shell graphs \(H(n_i, n_i – 3)\) is cordial. In this paper, we settle this conjecture affirmatively.
In this paper, we give formulas for the sums of generalized order-\(k\) Fibonacci, Pell, and similar other sequences, which we obtain using matrix methods. As applications, we give explicit formulas for the Tribonacci and Tetranacci numbers.
A \((g, f)\)-coloring is a generalized edge-coloring in which each color appears at each vertex \(v\) at least \(g(v)\) and at most \(f(v)\) times, where \(g(v)\) and \(f(v)\) are nonnegative and positive integers assigned to each vertex \(v\), respectively. The minimum number of colors used by a \((g, f)\)-coloring of \(G\) is called the \((g, f)\)-chromatic index of \(G\). The maximum number of colors used by a \((g, f)\)-coloring of \(G\) is called the upper \((g, f)\)-chromatic index of \(G\). In this paper, we determine the \((g, f)\)-chromatic index and the upper \((g, f)\)-chromatic index in some cases.
The Szeged index extends the Wiener index for cyclic graphs by counting the number of atoms on both sides of each bond and summing these counts. This index was introduced by Ivan Gutman at the Attila Jozsef University in Szeged in \(1994\), and is thus called the Szeged index. In this paper, we introduce a novel method for enumerating by cuts. Using this method, an exact formula for the Szeged index of a zig-zag polyhex nanotube \(T = TUHC_6{[p,q]}\) is computed for the first time.
In this study, we showed that an \((n+1)\)-regular linear space, which is the complement of a linear space having points not on \(m+1\) lines such that no three are concurrent in a projective subplane of odd order \(m\), \(m \geq 9\), could be embedded into a projective plane of order \(n\) as the complement of Ostrom’s hyperbolic plane.
For general graphs \(G\), it is known \([6]\) that the minimal length of an addressing scheme, denoted by \(N(G)\), is less than or equal to \(|G| – 1\). In this paper, we prove that for almost all complete bipartite graphs \(K_{m,n}\), \(N(K_{m,n}) = |K_{m,n}| – 2\).
A vertex subversion strategy of a graph \(G\) is a set of vertices \(X \subseteq V(G)\) whose closed neighborhood is deleted from \(G\). The survival subgraph is denoted by \(G/X\). The vertex-neighbor-integrity of \(G\) is defined to be \(VNI(G) = \min\{|X| + r(G/X) : X \subseteq V(G)\},\) where \(r(G/X)\) is the order of a largest component in \(G/X\). This graph parameter was introduced by Cozzens and Wu to measure the vulnerability of spy networks. It was proved by Gambrell that the decision problem of computing the vertex-neighbor-integrity of a graph is NP-complete. In this paper, we evaluate the vertex-neighbor-integrity of the composition graph of two paths.
In this paper, we prove that a matroid with at least two elements is connected if and only if it can be obtained from a loop by a nonempty sequence of non-trivial single-element extensions and series extensions.
Let \(G\) and \(H\) be graphs with a common vertex set \(V\), such that \(G – i \cong H – i\)for all \(i \in V\). Let \(p_i\) be the permutation of \(V – i\) that maps \(G – i\) to \(H – i\), and let \(q_i\) denote the permutation obtained from \(p_i\) by mapping \(i\) to \(i\). It is shown that certain algebraic relations involving the edges of \(G\) and the permutations \(q_iq_j^{-1}\) and \(q_iq_k^{-1}\), where \(i, j, k \in V\) are distinct vertices, often force \(G\) and \(H\) to be isomorphic.
The factorization of matrix \(A\) with entries \(a_{i,j}\) determined by \(a_{i,j} = \alpha a_{i-1,j-1} + \beta a_{i,j-1}\) is derived as \(A = TP^T\). An interesting factorization of matrix \(B\) with entries \(b_{i,j} = \alpha b_{i-1,j} + \beta b_{i,j-1}\) is given by \(B = P[\alpha]TP^{T}[\beta]\). The beautiful factorization of matrix \(C\) whose entries satisfy \(c_{i,j} = \alpha c_{i-1,j} + \beta c_{i-1,j-1} + Ye_{i-1,j-1}\) is founded to be \(C = P[\alpha]DP^T[\beta]\), where \(T\) is a Toeplitz matrix, and \(P\) and \(P[\alpha]\) are Pascal matrices. The matrix product factorization to the problem is solved perfectly so far.
Dirac showed that a \(2\)-connected graph of order \(n\) with minimum degree \(\delta\) has circumference at least \(\min\{2\delta, n\}\). We prove that a \(2\)-connected, triangle-free graph \(G\) of order \(n\) with minimum degree \(\delta\) either has circumference at least \(\min\{4\delta – 4, n\}\), or every longest cycle in \(G\) is dominating. This result is best possible in the sense that there exist bipartite graphs with minimum degree \(\delta\) whose longest cycles have length \(4\delta – 4\), and are not dominating.
The vertex linear arboricity \(vla(G)\) of a graph \(G\) is the minimum number of subsets into which the vertex set \(V(G)\) can be partitioned so that each subset induces a subgraph whose connected components are paths. It is proved here that \(\lceil \frac{\omega(G)}{2}\rceil \leq vla(G) \leq \lceil \frac{\omega(G)+1}{2}\rceil\) for a claw-free connected graph \(G\) having \(\Delta(G) \leq 6\), where \(\omega(G)\) is the clique number of \(G\).
An \(f\)-coloring of a graph \(G\) is a coloring of edges of \(E(G)\) such that each color appears at each vertex \(v \in V(G)\) at most \(f(v)\) times. The minimum number of colors needed to \(f\)-color \(G\) is called the \(f\)-chromatic index of \(G\) and denoted by \(\chi’_f(G)\). Any simple graph \(G\) has the \(f\)-chromatic index equal to \(\Delta_f(G)\) or \(\Delta_f(G) + 1\), where \(\Delta_f(G) = \max_{v \in V}\{\lceil \frac{d(v)} {f(v)}\rceil\}\). If \(\chi’_f(G) = \Delta_f(G)\), then \(G\) is of \(C_f\) \(1\); otherwise \(G\) is of \(C_f\) \(2\). In this paper, two sufficient conditions for a regular graph to be of \(C_f\) \(1\) or \(C_f\) \(2\) are obtained and two necessary and sufficient conditions for a regular graph to be of \(C_f\) \(1\) are also presented.
Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\), and let \(A\) be an abelian group. A labeling \(f: V(G) \to A\) induces an edge labeling \(f^*: E(G) \to A\) defined by \(f^*(xy) = f(x) + f(y)\), for each edge \(xy \in E(G)\). For \(i \in A\), let \(v_f(i) = \text{card}\{v \in V(G): f(v) = i\}\) and \(e_f(i) = \text{card}\{e \in E(G): f^*(e) = i\}\). Let \(c(f) = \{|e_f(i) – e_f(j)|: (i,j) \in A \times A\}\). A labeling \(f\) of a graph \(G\) is said to be \(A-friendly\) if \(|v_f(i) – v_f(j)| \leq 1\) for all \((i,j) \in A \times A\). If \(c(f)\) is a \((0,1)\)-matrix for an \(A\)-friendly labeling \(f\), then \(f\) is said to be \(A\)-cordial. When \(A = \mathbb{Z}_2\), the \({friendly index set}\) of the graph \(G\), \(FI(G)\), is defined as \(\{|e_f(0) – e_f(1)|: \text{the vertex labeling } f \text{ is } \mathbb{Z}_2\text{-friendly}\}\). In this paper, we determine the friendly index set of cycles, complete graphs, and some bipartite graphs.
In this paper, several constructions are presented for balanced incomplete block designs with nested rows and columns. Some of them refine theorems due to Hishida and Jimbo \([6]\) and Uddin and Morgan \([17]\), and some of them give parameters which have not been available before.
A vertex-distinguishing edge-coloring (VDEC) of a simple graph \(G\) which contains no more than one isolated vertex and no isolated edge is equitable (VDEEC) if the absolute value of the difference between the number of edges colored by color \(i\) and the number of edges colored by color \(j\) is at most one. The minimal number of colors needed such that \(G\) has a VDEEC is called the vertex-distinguishing equitable chromatic index of \(G\). In this paper, we propose two conjectures after investigating VDEECs on some special families of graphs, such as the stars, fans, wheels, complete graphs, complete bipartite graphs, etc.
The eccentricity \(e(v)\) of a vertex \(v\) in a strongly connected digraph \(G\) is the maximum distance from \(v\). The eccentricity sequence of a digraph is the list of eccentricities of its vertices given in non-decreasing order. A sequence of positive integers is a digraphical eccentric sequence if it is the eccentricity sequence of some digraph. A set of positive integers \(S\) is a digraphical eccentric set if there is a digraph \(G\) such that \(S = \{e(v), v \in V(G)\}\). In this paper, we present some necessary and sufficient conditions for a sequence \(S\) to be a digraphical eccentric sequence. In some particular cases, where either the minimum or the maximum value of \(S\) is fixed, a characterization is derived. We also characterize digraphical eccentric sets.
Let \(C_m\) be a cycle on \(m (\geq 3)\) vertices and let \(\ominus_{n-m}C_m\) denote the class of graphs obtained from \(C_m\) by adding \(n-m (\geq 1)\) distinct pendent edges to the vertices of \(C_m\). In this paper, it is proved that for every \(T\) in \(\ominus_{n-m}C_m\), the complete graph \(K_{2n+1}\) can be cyclically decomposed into the isomorphic copies of \(T\). Moreover, if \(m\) is even, then for every positive integer \(p\), the complete graph \(K_{2pn+1}\) can also be cyclically decomposed into the isomorphic copies of \(T\).
An aperiodic perfect map (APM) is an array with the property that each possible array of a given size, called a window, arises exactly once as a contiguous subarray in the array. In this paper, we give a construction method of an APM being a proper concatenation of some fragments of a given de Bruijn sequence. Firstly, we give a criterion to determine whether a designed sequence \(T\) with entries from the index set of a de Bruijn sequence can generate an APM. This implies a sufficient condition for being an APM. Secondly, two infinite families of APMs are given by constructions of corresponding sequences \(T\), respectively, satisfying the criterion.
We introduce a combinatorial shifting operation on multicomplexes that carries similar properties required for the ordinary shifting operation on simplicial complexes. A linearly colored simplicial complex is called shifted if its associated multicomplex is stable under defined operation. We show that the underlying simplicial subcomplex of a linearly shifted simplicial complex is shifted in the ordinary sense, while the ordinary and linear shiftings are not interrelated in general. Separately, we also prove that any linearly shifted complex must be shellable with respect to the order of its facets induced by the linear coloring. As an application, we provide a characterization of simple graphs whose independence complexes are linearly shifted. The class of graphs obtained constitutes a superclass of threshold graphs.
A local coloring of a graph \(G\) is a function \(c: V(G) \to \mathbb{N}\) having the property that for each set \(S \subseteq V(G)\) with \(2 \leq |S| \leq 3\), there exist vertices \(u,v \in S\) such that \(|c(u) – c(v)| \geq m_S\), where \(m_S\) is the size of the induced subgraph \(\langle S\rangle\). The maximum color assigned by a local coloring \(c\) to a vertex of \(G\) is called the value of \(c\) and is denoted by \(\chi_\ell(c)\). The local chromatic number of \(G\) is \(\chi_\ell(G) = \min\{\chi_\ell(c)\}\), where the minimum is taken over all local colorings \(c\) of \(G\). If \(\chi_\ell(c) = \chi_\ell(G)\), then \(c\) is called a minimum local coloring of \(G\). The local coloring of graphs introduced by Chartrand et al. in \(2003\). In this paper, following the study of this concept, first an upper bound for \(\chi_\ell(G)\) where \(G\) is not complete graphs \(K_4\) and \(K_5\), is provided in terms of maximum degree \(\Delta(G)\). Then the exact value of \(\chi_\ell(G)\) for some special graphs \(G\) such as the cartesian product of cycles, paths and complete graphs is determined.
Explicit expressions for all the primitive idempotents in the ring \(R_{2^n} = {F}_q[x]/(x^{2^n} – 1)\), where \(q\) is an odd prime power, are obtained. Some lower bounds on the minimum distances of the irreducible cyclic codes of length \(2^n\) over \({F}_q\) are also obtained.
In this note we prove that all connected Cayley graphs of every finite group \(Q \times H\) are \(1\)-factorizable, where \(Q\) is any non-trivial group of \(2\)-power order and \(H\) is any group of odd order.
A graph \(G\) is called super vertex-magic total labelings if there exists a bijection \(f\) from \(V(G) \cup E(G)\) to \(\{1,2,\ldots,|V(G)| + |E(G)|\}\) such that \(f(v) + \sum_{u \sim v} f(vu) = C\), where the sum is over all vertices \(u\) adjacent to \(v\) and \(f(V(G)) = \{1,2,\ldots,|V(G)|\}\), \(f(E(G)) = \{|V(G)|+1,|V(G)|+2,\ldots,|V(G)|+|E(G)|\}\). \({The Knödel graphs}\) \(W_{\Delta,n}\) have even \(n \geq 2\) vertices and degree \(\Delta\), \(1 \leq \Delta \leq \lfloor\log_2 n\rfloor\). The vertices of \(W_{\Delta,n}\) are the pairs \((i,j)\) with \(i = 1,2\) and \(0 \leq i \leq n/2-1\). For every \(j\), \(0 \leq j \leq n/2-1\), there is an edge between vertex \((1,j)\) and every vertex \((2,(j+2^k-1) \mod (n/2))\), for \(k=0,\ldots,\Delta-1\). In this paper, we show that \(W_{3,n}\) is super vertex-magic for \(n \equiv 0 \mod 4\).
Evolutionary graphs were initially proposed by Lieberman \(et \;al\). and evolutionary dynamics on two levels are recently introduced by Traulsen et al. We now introduce a new type of evolutionary dynamics,evolutionary graphs on two levels, and the fixation probability is analyzed. Some interesting results, evolutionary graphs on two levels are more stable than single level evolutionary graphs, are obtained in this paper.
A vertex \(k\)-ranking of a graph \(G\) is a function \(c: V(G) \to \{1,\ldots,k\}\) such that if \(c(u) = c(v)\), \(u,v \in V(G)\), then each path connecting vertices \(u\) and \(v\) contains a vertex \(w\) with \(c(w) > c(u)\). If each vertex \(v\) has a list of integers \(L(v)\) and for a vertex ranking \(c\) it holds \(c(v) \in L(v)\) for each \(v \in V(G)\), then \(c\) is called an \(L\)-list \(k\)-ranking, where \(\mathcal{L} = \{L(v) : v \in V(G)\}\). In this paper, we investigate both vertex and edge (vertex ranking of a line graph) list ranking problems. We prove that both problems are NP-complete for several classes of acyclic graphs, like full binary trees, trees with diameter at most \(4\), and comets. The problem of finding vertex (edge) \(\mathcal{L}\)-list ranking is polynomially solvable for paths and trees with a bounded number of non-leaves, which includes trees with diameter less than \(4\).
In this paper we determine unique graph with largest spectral radius among all tricyclic graphs with \(n\) vertices and \(k\) pendant edges.
A new proof is given to the following result of ours. Let \(G\) be an outerplanar graph with maximum degree \(\Delta \geq 3\). The chromatic number \(\chi(G^2)\) of the square of \(G\) is at most \(\Delta+2\), and \(\chi(G^2) = \Delta+1\) if \(\Delta \geq 7\).
Some designs using the action of the linear fractional groups \(L_2(q)\), \(q = 11, 13, 16, 17, 19, 23\) are constructed. We will show that \(L_2(q)\) or its automorphism group acts as the full automorphism group of each of the constructed designs except in the case \(q = 16\). For designs constructed from \(L_2(16)\), we will show that \(L_2(16)\), \(L_2(16) : 2\), \(L_2(16) : 4\) or \(S_{17}\) can arise as the full automorphism group of the design.
For odd \(n \geq 5\), the Flower Snark \(F_n = (V, E)\) is a simple undirected cubic graph with \(4n\) vertices, where \(V = \{a_i : 0 \leq i \leq n-1\} \cup \{b_i : 0 \leq i \leq n-1\} \cup \{c_i : 0 \leq i \leq 2n-1\}\) and \(E = \{b_ib_{(i+1)\mod(n)}: 0 \leq i \leq n-1\} \cup \{c_ic_{(i+1)\mod(2n)} : 0 \leq i \leq 2n-1\} \cup \{a_ib_i,a_ic_i,a_ic_{n+i} : 0 \leq i \leq n-1\}\). For \(n = 3\) or even \(n \geq 4\), \(F_n\) is called the related graph of Flower Snark. We show that the crossing number of \(F_n\) equals \(n – 2\) if \(3 \leq n \leq 5\), and \(n\) if \(n \geq 6\).
A subset \(S\) of the vertex set of a graph \(G\) is called acyclic if the subgraph it induces in \(G\) contains no cycles. We call \(S\) an acyclic dominating set if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by \(\gamma_a(G)\), is called the acyclic domination number of \(G\). A graph \(G\) is \({2-diameter-critical}\) if it has diameter \(2\) and the deletion of any edge increases its diameter. In this paper, we show that for any positive integers \(k\) and \(d \geq 3\), there is a \(2\)-diameter-critical graph \(G\) such that \(\delta(G) = d\) and \(\gamma_a(G) – \delta(G) \geq k\), and our result answers a question posed by Cheng et al. in negative.
A function \(f: V \to \{1,\ldots,k\}\) is a broadcast coloring of order \(k\) if \(\pi(u) = \pi(v)\) implies that the distance between \(u\) and \(v\) is more than \(\pi(u)\). The minimum order of a broadcast coloring is called the broadcast chromatic number of \(G\), and is denoted \(\chi_b(G)\). In this paper we introduce this coloring and study its properties. In particular, we explore the relationship with the vertex cover and chromatic numbers. While there is a polynomial-time algorithm to determine whether \(\chi_b(G) \leq 3\), we show that it is \(NP\)-hard to determine if \(\chi_b(G) \leq 4\). We also determine the maximum broadcast chromatic number of a tree, and show that the broadcast chromatic number of the infinite grid is finite.
A connected graph \(G = (V, E)\) is said to be \((a,d)\)-antimagic if there exist positive integers \(a,d\) and a bijection \(f : E \to \{1,2,\ldots,|E|\}\) such that the induced mapping \(g_f : V \to \mathbb{N}\), defined by \(g_f(v) = \sum f(uv)\),\({uv \in E(G)}\) is injective and \(g_f(V) = \{a,a+d,\ldots,a+(|V|-1)d\}\). Mirka Miller and Martin Bača proved that the generalized Petersen graph \(P(n, 2)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for \(n \equiv 0 \pmod{4}\), \(n \geq 8\) and conjectured that the generalized Petersen graph \(P(n, k)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n\) and \(2 \leq k \leq \frac{n}{2}-1\). In this paper, we show that the generalized Petersen graph \(P(n, 3)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n \geq 8\).
In this paper, we derive new recurrence relations and generating matrices for the sums of usual Tribonacci numbers and \(4n\) subscripted Tribonacci sequences, \(\{T_{4n}\}\), and their sums. We obtain explicit formulas and combinatorial representations for the sums of terms of these sequences. Finally, we represent relationships between these sequences and permanents of certain matrices.
Let \(\mathcal{K} = (K_{ij})\) be an infinite lower triangular matrix of non-negative integers such that \(K_{i0} = 1\) and \(K_{ii} \geq 1\) for \(i \geq 0\). Define a sequence \(\{V_i(\mathcal{K})\}_{m\geq0}\) by the recurrence \(V_{i+1}(\mathcal{K}) = \sum_{j=0}^m K_{mj}V_j(\mathcal{K})\) with \(V_0(\mathcal{K}) = 1\). Let \(P(n;\mathcal{K})\) be the number of partitions of \(n\) of the form \(n = p_1 + p_2 + p_3 + p_4 + \cdots\) such that \(p_j \geq \sum_{i\geq j} K_{ij}p_{i+1}\) for \(j \geq 1\) and let \(P(n;V(\mathcal{K}))\) denote the number of partitions of \(n\) into summands in the set \(V(\mathcal{K}) = \{V_1(\mathcal{K}), V_2(\mathcal{K}), \ldots\}\). Based on the technique of MacMahon’s partitions analysis, we prove that \(P(n;\mathcal{K}) = P(n;V(\mathcal{K}))\) which generalizes a recent result of Sellers’. We also give several applications of this result to many classical sequences such as Bell numbers, Fibonacci numbers, Lucas numbers, and Pell numbers.
Minimal blocking sets of class \([h,k]\) with respect to the external lines to an elliptic quadric of \(\text{PG}(3,q)\), \(q \geq 5\) prime, are characterized.
For every integer \(c\) and every positive integer \(k\), let \(n = r(c, k)\) be the least integer, provided that it exists, such that for every coloring
\[\Delta: \{1,2,\ldots,n\} \rightarrow \{0,1\},\]
there exist three integers, \(x_1, x_2, x_3\), (not necessarily distinct) such that
\[\Delta(x_1) = \Delta(x_2) = \Delta(x_3)\]
and
\[x_1+x_2+c= kx_3.\]
If such an integer does not exist, then let \(r(c, k) = \infty\). The main result of this paper is that
\[r(c,2) =
\begin{cases}
|c|+1 & \text{if } c \text{ is even} \\
\infty & \text{if } c \text{ is odd}
\end{cases}\]
for every integer \(c\). In addition, a lower bound is found for \(r(c, k)\) for all integers \(c\) and positive integers \(k\) and linear upper and lower bounds are found for \(r(c, 3)\) for all positive integers \(c\).
Let \(C_n\) denote the cycle with \(n\) vertices, and \(C_n^{(t)}\) denote the graphs consisting of \(t\) copies of \(C_n\) with a vertex in common. Koh et al. conjectured that \(C_n^{(t)}\) is graceful if and only if \(nt \equiv 0,3 \pmod 4\). The conjecture has been shown true for \(n = 3,5,6,7,4k\). In this paper, the conjecture is shown to be true for \(n = 9\).
In this paper, we define the hyperbolic modified Pell functions by the modified Pell sequence and classical hyperbolic functions. Afterwards, we investigate the properties of the modified Pell functions.
Deza and Grishukhin studied \(3\)-valent maps \(M_n{(p,q)}\) consisting of a ring of \(n\) \(g\)-gons whose inner and outer domains are filled by \(p\)-gons. They described the conditions for \(n, p, q\) under which such a map may exist and presented several infinite families of them. We extend their results by presenting several new maps concerning mainly large values of \(n\) and \(q\).
A simple, undirected \(2\)-connected graph \(G\) of order \(n\) belongs to the class \(\mathcal{B}(n,\theta)\), \(\theta \geq 0\) if \(2(d(x) + d(y) + d(z)) \geq 3(n – 1 – \theta)\) holds for all independent triples \(\{x,y,z\}\) of vertices. It is known (Bondy’s theorem for \(2\)-connected graphs) that \(G\) is hamiltonian if \(\theta = 0\). In this paper we give a full characterization of graphs \(G\) in \(\mathcal{B}(n,\theta)\), \(\theta \leq 2\) in terms of their dual hamiltonian closure.
Two classes of regular Cayley maps, balanced and antibalanced, have long been understood, see \([12,11]\). A recent generalization is that of an e-balanced map, see \([7,2,5,8]\). These maps can be described using the power function introduced in \([4]\); e-balanced maps are the ones with constant power functions on the generating set. In this paper we examine a further generalization to the situation where the power function alternates between two values.
In this paper, we obtain the spectral norm and eigenvalues of circulant matrices with Horadam’s numbers. Furthermore, we define the semicirculant matrix with these numbers and give the Euclidean norm of this matrix.
We denote by \(G(n)\) the graph obtained by removing a Hamilton cycle from the complete graph \(K_n\). In this paper, we calculate the lower bound for the minimum number of monochromatic triangles in any \(2\)-edge coloring of \(G(n)\) using the weight method. Also, by explicit constructions, we give an upper bound for the minimum number of monochromatic triangles in \(2\)-edge coloring of \(G(n)\) and the difference between our lower and upper bound is just two.
In this paper, it is proved that the \(h\)-chromatic uniqueness of the linear \(h\)-hypergraph consisting of two cycles of lengths \(p\) and \(q\) having \(r\) edges in common when \(p=q\), \(2 \leq r \leq p-2\), and \(h \geq 3\). We also obtain the chromatic polynomial of a connected unicyclic linear \(h\)-hypergraph and show that every \(h\)-uniform cycle of length three is not chromatically unique for \(h \geq 3\).
The projection of binary linear block codes of length \(4m\) on \(\mathbb{F}_4^m\) is considered. Three types of projections, namely projections \(SE\), \(E\), and \(O\) are introduced. The BCH codes, Golay codes, Reed-Muller codes, and the quadratic residue code \(q_{32}\) are examined.
The hyper Wiener index of a connected graph \(G\) is defined as
\(WW(G) = \frac{1}{2}\sum_{u,v \in V(G)} d(u,v) + \frac{1}{2}\sum_{(u,v) \in V(G)} d(u,v)^2\) where \(d(u, v)\) is the distance between vertices \(u,v \in V(G)\).
In this paper we find an exact expression for hyper Wiener index of \(HC_6[p, q]\), the zigzag polyhex nanotori.
In this paper, we classify all optimal linear \([n, n/2]\) codes over \(\mathbb{Z}_4\) up to length \(n = 8\), and determine the number of optimal codes which are self-dual and formally self-dual. Optimal codes with linear binary images are identified. In particular, we show that for length \(8\), there are nine optimal codes for the Hamming distance, one optimal code for the Lee distance, and two optimal codes for the Euclidean distance.
In this paper, we show that if \(k \geq \frac{v+2}{4}\), where \(v\) denotes the order of a graph, a non-bipartite graph \(G\) is \(k\)-extendable if and only if it is \(2k\)-factor-critical. If \(k \geq \frac{v-3}{4}\), a graph \(G\) is \(k\)-extendable if and only if it is \((2k+1)\)-factor-critical. We also give examples to show that the two bounds are best possible. Our results are answers to a problem posted by Favaron \([3]\) and Yu \([11]\).
The edge-neighbor-scattering number of a graph \(G\) is defined to be \(EN_S(G) = \max\limits_{S\subseteq E(G)}\{w(G/S) -\mid |S|\}\) where \(S\) is any edge-cut-strategy of \(G\), \(w(G/S)\) is the number of the components of \(G/S\). In this paper, we give edge-neighbor-scattering number of some special classes of graphs, and then mainly discuss the general properties of the parameter.
Let \(F(x,y) = ax^2 + bxy + cy^2\) be a binary quadratic form of discriminant \(\Delta = b^2 – 4ac\) for \(a,b,c \in \mathbb{Z}\), let \(p\) be a prime number and let \(\mathbb{F}_p\) be a finite field. In this paper we formulate the number of integer solutions of cubic congruence \(x^3 + ax^2 + bx + c \equiv 0 \pmod{p}\) over \(\mathbb{F}_p\), for two specific binary quadratic forms \(F_1^k(x,y) = x^2 + kxy + ky^2\) and \(F_2^k(x,y) = kx^2 + kxy + k^2y^2\) for integer \(k\) such that \(1 \leq k \leq 9\). Later we consider representation of primes by \(F_1^k\) and \(F_2^k\).
A subset \(S \subseteq V(G)\) is independent if no two vertices of \(S\) are adjacent in \(G\). In this paper we study the number of independent sets which meets the set of leaves in a tree. In particular we determine the smallest number and the largest number of these sets among \(n\)-vertex trees. In each case we characterize the extremal graphs.
A graph \(G\) is called super edge-magic if there exists a bijection \(f\) from \(V(G) \cup E(G)\) to \(\{1,2,\ldots,|V(G)| + |E(G)|\}\) such that \(f(u) + f(v) + f(uv) = k\) is a constant for any \(uv \in E(G)\) and \(f(V(G)) = \{1,2,\ldots,|V(G)|\}\). Yasuhiro Fukuchi proved that the generalized Petersen graph \(P(n, 2)\) is super edge-magic for odd \(n \geq 3\). In this paper, we show that the generalized Petersen graph \(P(n,3)\) is super edge-magic for odd \(n \geq 5\).
For any integer \(k\), two tournaments \(T\) and \(T’\), on the same finite set \(V\) are \(k\)-similar, whenever they have the same score vector, and for every tournament \(H\) of size \(k\) the number of subtournaments of \(T\) (resp. \(T’\)) isomorphic to \(H\) is the same. We study the \(4\)-similarity. According to the decomposability, we construct three infinite classes of pairs of non-isomorphic \(4\)-similar tournaments.
In this paper, we define the Pell and Pell-Lucas \(p\)-numbers and derive the analytical formulas for these numbers. These formulas are similar to Binet’s formula for the classical Pell numbers.
A graph \(G\) is called resonant if the boundary of each face of \(G\) is an \(F\)-alternating closed trail with respect to some \(f\)-factor \(F\) of \(G\). We show that a plane bipartite graph \(G\) is resonant if and only if it is connected and each edge of \(G\) is contained in an \(f\)-factor and not in another \(f\)-factor.
Let \(P_k\) denote a path with \(k\) vertices and \(k-1\) edges. And let \(\lambda K_{n,n}\) denote the \(\lambda\)-fold complete bipartite graph with both parts of size \(n\). A \(P_k\)-decomposition \(\mathcal{D}\) of \(\lambda K_{n,n}\) is a family of subgraphs of \(\lambda K_{n,n}\) whose edge sets form a partition of the edge set of \(\lambda K_{n,n}\), such that each member of \(\mathcal{G}\) is isomorphic to \(P_k\). Necessary conditions for the existence of a \(P_k\)-decomposition of \(\lambda K_{n,n}\) are (i) \(\lambda n^2 \equiv 0 \pmod{k-1}\) and (ii) \(k \leq n+1\) if \(\lambda=1\) and \(n\) is odd, or \(k \leq 2n\) if \(\lambda \geq 2\) or \(n\) is even. In this paper, we show these necessary conditions are sufficient except for the possibility of the case that \(k=3\), \(n=15\), and \(k=28\).
We describe a technique for producing self-dual codes over rings and fields from symmetric designs. We give special attention to biplanes and determine the minimum weights of the codes formed from these designs. We give numerous examples of self-dual codes constructed including an optimal code of length \(22\) over \(\mathbb{Z}_4\) with respect to the Hamming metric from the biplane of order \(3\).
The distance graph \(G(S, D)\) has vertex set \(V(G(S, D)) = S \cup \mathbb{R}^n\) and two vertices \(u\) and \(v\) are adjacent if and only if their distance \(d(u, v)\) is an element of the distance set \(D \subseteq \mathbb{R}_+\).
We determine the chromatic index, the choice index, the total chromatic number and the total choice number of all distance graphs \(G(\mathbb{R}, D)\), \(G(\mathbb{Q}, D)\) and \(G(\mathbb{Z}, D)\) transferring a theorem of de Bruijn and Erdős on infinite graphs. Moreover, we prove that \(|D| + 1\) is an upper bound for the chromatic number and the choice number of \(G(S,D)\), \(S \subseteq \mathbb{R}\).
