
Let \( G \) be the one-point union of two cycles and suppose \( G \) has \( n \) edges. We show via various graph labelings that there exists a cyclic \( G \)-decomposition of \( K_{2nt+1} \) for every positive integer \( t \).
Recently Ozbal and Firat [22] introduced the notion of symmetric \( f \) bi-derivation of a lattice. They give illustrative examples and they also characterized the distributive lattice by symmetric \( f \) bi-derivation. In this paper, we define the isotone symmetric \( f \) bi-derivation and obtain some interesting results about isotoneness. We also provide the relations between distributive, modular, and isotone lattices through symmetric \( f \) bi-derivation.
In 2003, Lee, Wang and Wen found a non-edge-magic simple connected cubic graph which satisfying the necessary condition of edge-magicness by using computer search. They asked for a mathematical proof. In this paper, we will provide such a proof.
Let \( G \) be a graph and let \( f \) be a positive integer-valued function defined on \( V(G) \) such that \( 1 \leq a \leq f(x) \leq b \leq 2a \) for every \( x \in V(G) \). If \( t(G) \geq \frac{b^2}{a} \), \( |V(G)| \geq \frac{b^2}{a} + 1 \), and \( f(V(G)) \) is even, then \( G \) has an \( f \)-factor.
A general construction for \( t \)-SB(\(2t-1\), \(2t-2\)) designs is given. In addition, large sets of \( t \)-SB(\(v\), \(k\)) are discussed and some examples are provided.
For a poset \( P = (X, \leq_P) \), the strict-double-bound graph (\(sDB\)-graph) of \( P = (X, \leq_P) \) is the graph \( sDB(P) \) on \( X \) for which vertices \( u \) and \( v \) of \( sDB(P) \) are adjacent if and only if \( u \neq v \) and there exist \( x \) and \( y \) in \( X \) distinct from \( u \) and \( v \) such that \( x \leq u \leq y \) and \( x \leq v \leq y \). The strict-double-bound number \( \zeta(G) \) is defined as
\[
\zeta(G) = \min \{ n \mid G \cup N_n \text{ is a strict-double-bound graph} \},
\]
where \( N_n \) is the graph with \( n \) vertices and no edges.
In this paper we deal with strict-double-bound numbers of some graphs. For example, we obtain that
\[
\zeta(P_n) = \lceil 2\sqrt{n-1} \rceil \text{ (} n \geq 2 \text{)},
\]
\[
\zeta(C_n) = \lceil 2\sqrt{n} \rceil \text{ (} n \geq 4 \text{)},
\]
\[
\zeta(W_n) = \lceil 2\sqrt{n-1} \rceil \text{ (} n \geq 5 \text{)},
\]
and
\[
\zeta(G + K_n) = \zeta(G)
\]
for a graph \( G \) with no isolated vertices.
The metric dimension of a graph \(G\), denoted by \(\text{dim}(G)\), is the minimum number of vertices such that all vertices are uniquely determined by their distances to the chosen vertices. For a graph \(G\) and its complement \(\overline{G}\), each of order \(n \geq 4\) and connected, we show that
\[
2 \leq \text{dim}(G) + \text{dim}(\overline{G}) \leq 2(n-3).
\]
It is readily seen that \(\text{dim}(G) + \text{dim}(\overline{G}) = 2\) if and only if \(n = 4\). We characterize graphs satisfying
\[
\text{dim}(G) + \text{dim}(\overline{G}) = 2(n-3)
\]
when \(G\) is a tree or a unicyclic graph.
Whist tournament designs are known to exist for all \( v \equiv 0,1 \pmod{4} \). Much less is known about the existence of \(\mathbb{Z}\)-cyclic whist designs. Previous studies \([5, 6]\) have reported on all \(\mathbb{Z}\)-cyclic whist designs for \( v \in \{4,5,8,9,12,13,16,17,20,21,24,25\} \). This paper is a report on all \(\mathbb{Z}\)-cyclic whist tournament designs on 28 players, including a detailed summary of all known whist specializations related to a 28 player \(\mathbb{Z}\)-cyclic whist design. Our study shows that there are \( 7,910,127 \) \(\mathbb{Z}\)-cyclic whist designs on 28 players. Of these designs, \( 2,568,510 \) possess the Three Person Property, \( 240,948 \) possess the Triplewhist Property and none possess the Balancedwhist Property. Introduced here is the concept of the mirror image of a \(\mathbb{Z}\)-cyclic whist design. In general, utilization of this concept reduces the computer search for \(\mathbb{Z}\)-cyclic whist designs by nearly fifty percent.
Let \( S \) be an orthogonal polygon in the plane bounded by a simple closed curve. Assume that every two boundary points of \( S \) have a common staircase illuminator whose edges are north and east. Then \( S \) contains a staircase path \( \mu_0 \) whose edges are north and east such that \( \mu_0 \) illumines every point of \( S \). Without the requirement that the illuminators share a common direction, the result fails.
The upper domination Ramsey number \(u(3, 3, 3)\) is the smallest integer \(n\) such that every \(3\)-coloring of the edges of complete graph \(K_n\) contains a monochromatic graph \(G\) with \(\Gamma(\overline{G}) \geq 3\), where \(\Gamma(\overline{G})\) is the maximum order over all the minimal dominating sets of the complement of \(G\). In this note, with the help of computers, we determine that \(U(3, 3, 3) = 13\), which improves the results that \(13 \leq U(3, 3, 3) \leq 14\) provided by Michael A. Henning and Ortrud R. Oellermann.
Let \(G\) be a graph of order \(n \geq 4k+8\), where \(k\) is a positive integer with \(kn\) even and \(\delta(G) > k+1\). We show that if \(max\{d_G(u),d_G(v)\} > {n}/{2}\) for each pair of nonadjacent vertices \(u,v\), then \(G\) has a connected \([k, k+1]\)-factor excluding any given edge \(e\).
A \( k \)-edge labeling of a graph \( G \) is a function \( f \) from the edge set \( E(G) \) to the set of integers \( \{0, \ldots, k-1\} \). Such a labeling induces a labeling \( f \) on the vertex set \( V(G) \) by defining \( f(v) = \sum f(e) \), where the summation is taken over all the edges incident on the vertex \( v \) and the value is reduced modulo \( k \). Cahit calls this labeling edge-\( k \)-equitable if \( f \) assigns the labels \( \{0, \ldots, k-1\} \) equitably to the vertices as well as edges.
If \( G_1, \ldots, G_T \) is a family of graphs having a graph \( H \) as an induced subgraph, then by \( H \)-union \( G \) of this family we mean the graph obtained by identifying all the corresponding vertices as well as edges of the copies of \( H \) in \( G_1, \ldots, G_T \).
In this paper we prove that the \( \overline{K}_n \)-union of gears is edge-\( 3 \)-equitable.
Let \( k \) be a positive integer and let \( G \) be a simple graph with vertex set \( V(G) \). If \( v \) is a vertex of \( G \), then the open \( k \)-neighborhood of \( v \), denoted by \( N_{k,G}(v) \), is the set \( N_{k,G}(v) = \{u \mid u \neq v \text{ and } d(u, v) \leq k\} \). The closed \( k \)-neighborhood of \( v \), denoted by \( N_{k,G}[v] \), is \( N_{k,G}[v] = N_{k,G}(v) \cup \{v\} \). A function \( f: V(G) \to \{-1,1\} \) is called a \({signed\; distance \; k -dominating\; function}\) if \( \sum_{u \in N_{k,G}(v)} f(u) \geq 1 \) for each vertex \( v \in V(G) \). A set \( \{f_1, f_2, \ldots, f_d\} \) of signed distance \( k \)-dominating functions on \( G \) with the property that \( \sum_{i=1}^d f_i(v) \leq 1 \) for each \( v \in V(G) \) is called a \({signed\; distance \; k -dominating \;family}\) (of functions) on \( G \). The maximum number of functions in a signed distance \( k \)-dominating family on \( G \) is the \({signed\; distance \; k -domatic\; number}\) of \( G \), denoted by \( d_{k,s}(G) \). Note that \( d_{1,s}(G) \) is the classical signed domatic number \( d_s(D) \). In this paper, we initiate the study of signed distance \( k \)-domatic numbers in graphs and we present some sharp upper bounds for \( d_{k,s}(G) \).
We associate each endomorphism of a finite cyclic group with a digraph and study many properties of this digraph, including its adjacency matrix and automorphism group.
In this paper, we consider a variation of toughness, and prove stronger results for the existence of \([a, b]\)-factors. Furthermore, we show that the results are sharp in some sense.
A decomposition \( \mathcal{D} \) of a graph \( H \) by a graph \( G \) is a partition of the edge set of \( H \) such that the subgraph induced by the edges in each part of the partition is isomorphic to \( G \). The intersection graph \( I(\mathcal{D}) \) of the decomposition \( \mathcal{D} \) has a vertex for each part of the partition and two parts \( A \) and \( B \) are adjacent if and only if they share a common node in \( H \). If \( I(\mathcal{D}) \cong H \), then \( \mathcal{D} \) is an automorphic decomposition of \( H \). If \( n(G) = \chi(H) \) as well, then we say that \( \mathcal{D} \) is a fully automorphic decomposition. In this paper, we examine the question of whether a fully automorphic host will have an even degree of regularity. We also give several examples of fully automorphic decompositions as well as necessary conditions for their existence.
A modular \(k\)-coloring, \(k \geq 2\), of a graph \(G\) without isolated vertices is a coloring of the vertices of \(G\) with the elements in \(\mathbb{Z}_k\) (where adjacent vertices may be colored the same) having the property that for every two adjacent vertices in \(G\) the sums of the colors of their neighbors are different in \(\mathbb{Z}_k\). The minimum \(k\) for which \(G\) has a modular \(k\)-coloring is the modular chromatic number mc\((G)\) of \(G\). It is known that \(2 \leq \text{mc}(T) \leq 3\) for every nontrivial tree \(T\). We present an efficient algorithm that computes the modular chromatic number of a given tree.
In this note, we consider the \(i\)-block intersection graphs (\(i\)-BIG) of a universal friendship \(3\)-hypergraph and show that they are pancyclic for \(i = 1,2\). We also show that the \(1\)-BIG of a universal friendship \(3\)-hypergraph is Hamiltonian-connected.
We study samples \(\Gamma = (\Gamma_1, \ldots, \Gamma_n)\) of length \(n\) where the letters \(\Gamma_i\) are independently generated according to the geometric distribution \(\mathbb{P}(\Gamma_j = i) = pq^{i-1}\), for \(1 \leq j \leq n\), with \(p+q=1\) and \(0<p<1\). An \({up-smooth\; sample}\) \(\Gamma\) is a sample such that \(\Gamma_{i+1}- \Gamma_i \leq 1\). We find generating functions for the probability that a sample of \(n\) geometric variables is up-smooth, with or without a specified first letter. We also extend the up-smooth results to words over an alphabet of \(k\) letters and to compositions of integers. In addition, we study smooth samples \(T\) of geometric random variables, where the condition now is \(|\Gamma_{i+1}- \Gamma_i| \leq 1\).
A Roman dominating function on a graph \(G = (V, E)\) is a function \(f : V \to \{0,1,2\}\) satisfying the condition that every vertex \(u \in V\) for which \(f(u) = 0\) is adjacent to a vertex \(v\) for which \(f(v) = 2\). The weight of a Roman dominating function is the value \(f(V) = \sum_{u \in V} f(u)\). The Roman domination number, \(\gamma_R(G)\), of \(G\) is the minimum weight of a Roman dominating function on \(G\). In this paper, we study those graphs for which the removal of any pair of vertices decreases the Roman domination number. A graph \(G\) is said to be \emph{Roman domination bicritical} or just \(\gamma_R\)-bicritical, if \(\gamma_R(G – \{v,u\}) < \gamma_R(G)\) for any pair of vertices \(v,u \in V\). We study properties of \(\gamma_R\)-bicritical graphs, and we characterize \(\gamma_R\)-bicritical trees and unicyclic graphs.
The van der Waerden number \(W(r, k)\) is the least integer \(N\) such that every \(r\)-coloring of \(\{1, 2, \ldots, N\}\) contains a monochromatic arithmetic progression of length at least \(k\). Rabung gave a method to obtain lower bounds on \(W(2, k)\) based on quadratic residues, and performed computations on all primes no greater than \(20117\). By improving the efficiency of the algorithm of Rabung, we perform the computation for all primes up to \(6 \times 10^7\), and obtain lower bounds on \(W(2, k)\) for \(k\) between \(11\) and \(23\).
Let \( G = (V, E) \) be a graph with chromatic number \( k \). A dominating set \( D \) of \( G \) is called a chromatic transversal dominating set (ctd-set) if \( D \) intersects every color class of any \( k \)-coloring of \( G \). The minimum cardinality of a ctd-set of \( G \) is called the chromatic transversal domination number of \( G \) and is denoted by \( \gamma_{ct}(G) \). In this paper, we obtain sharp upper and lower bounds for \( \gamma_{ct} \) for the Mycielskian \( \mu(G) \) and the shadow graph \( \text{Sh}(G) \) of any graph \( G \). We also prove that for any \( c \geq 2 \), the decision problem corresponding to \( \gamma_{ct} \) is NP-hard for graphs with \( \chi(G) = c \).
Let \( G(V, E) \) be a simple graph, and let \( f \) be an integer function defined on \( V \) with \( 1 \leq f(v) \leq d(v) \) for each vertex \( v \in V \). An \( f \)-edge covered colouring is an edge colouring \( C \) such that each colour appears at each vertex \( v \) at least \( f(v) \) times. The maximum number of colours needed to \( f \)-edge covered colour \( G \) is called the \( f \)-edge covered chromatic index of \( G \) and denoted by \( \chi_{fc}'(G) \). Any simple graph \( G \) has an \( f \)-edge covered chromatic index equal to \( \delta_f \) or \( \delta_f – 1 \), where \( \delta_f = \min \left\{\left\lfloor\frac{d(v)}{f(v)}\right\rfloor : v \in V(G)\right\} \). Let \( G \) be a connected and not complete graph with \( \chi_{fc}’ = \delta_f – 1 \). If for each \( u, v \in V \) and \( e = uv \notin E \), we have \( \chi_{fc}'(G+e) > \chi_{fc}'(G) \); then \( G \) is called an \( f \)-edge covered critical graph. In this paper, some properties of \( f \)-edge covered critical graphs are discussed. It is proved that if \( G \) is an \( f \)-edge covered critical graph, then for each \( u, v \in V \) and \( e = uv \notin E \) there exists \( w \in \{u, v\} \) with \( d(w) \leq \delta_f(f(w) + 1) – 2 \) such that \( w \) is adjacent to at least \( \max \left\{d(w) – \delta_f f(w) + 1, (f(w) + 2)d(w) – \delta_f(f(w) + 1)^2 + f(w) + 3\right\} \) vertices which are all \( \delta_f \)-vertices in \( G \).
We answer in the affirmative a question posed by Al-Addasi and Al-Ezeh in 2008 on the existence of symmetric diametrical bipartite graphs of diameter 4. Bipartite symmetric diametrical graphs are called \( S \)-graphs by some authors, and diametrical graphs have also been studied by other authors using different terminology, such as self-centered unique eccentric point graphs. We include a brief survey of some of this literature and note that the existence question was also answered by Berman and Kotzig in a 1980 paper, along with a study of different isomorphism classes of these graphs using a \( (1,-1) \)-matrix representation which includes the well-known Hadamard matrices. Our presentation focuses on a neighborhood characterization of \( S \)-graphs, and we conclude our survey with a beautiful version of this characterization known to Janakiraman.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.