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\le a\le f(x)\le b\le 2a$ for every $x\in V(G)$. If $t(G)\ge \frac{b^2}{a}$, $|V(G)|\ge \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,{\le }_P)$, the strict-double-bound graph ($sDB$-graph) of $P=(X,{\le }_P)$ is the graph $sDB(P)$ on $X$ for which vertices $u$ and $v$ of $sDB(P)$ are adjacent if and only if $u\ne v$ and there exist $x$ and $y$ in $X$ distinct from $u$ and $v$ such that $x\le u\le y$ and $x\le v\le 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\ge 2\text{)},$$

$$\zeta (C_n)=\lceil 2\sqrt{n}\rceil \text{ (}n\ge 4\text{)},$$

$$\zeta (W_n)=\lceil 2\sqrt{n-1}\rceil \text{ (}n\ge 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\ge 4$ and connected, we show that

$$2\le \text{dim}(G)+\text{dim}(\overline{G})\le 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(\mathrm{mod}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 $\mathrm{\Gamma }(\overline{G})\ge 3$, where $\mathrm{\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\le U(3,3,3)\le 14$ provided by Michael A. Henning and Ortrud R. Oellermann.

Let $G$ be a graph of order $n\ge 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,\dots ,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,\dots ,k-1\}$ equitably to the vertices as well as edges.

If $G_1,\dots ,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,\dots ,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\ne v\text{ and }d(u,v)\le 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 $signeddistancek-dominatingfunction$ if $\sum _{u\in N_{k,G}(v)}f(u)\ge 1$ for each vertex $v\in V(G)$. A set $\{f_1,f_2,\dots ,f_d\}$ of signed distance $k$-dominating functions on $G$ with the property that $\sum _{i=1}^d{f}_i(v)\le 1$ for each $v\in V(G)$ is called a $signeddistancek-dominatingfamily$ (of functions) on $G$. The maximum number of functions in a signed distance $k$-dominating family on $G$ is the $signeddistancek-domaticnumber$ 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\ge 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\le \text{mc}(T)\le 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 $\mathrm{\Gamma }=({\mathrm{\Gamma }}_1,\dots ,{\mathrm{\Gamma }}_n)$ of length $n$ where the letters ${\mathrm{\Gamma }}_i$ are independently generated according to the geometric distribution $\mathbb{P}({\mathrm{\Gamma }}_j=i)=p{q}^{i-1}$, for $1\le j\le n$, with $p+q=1$ and $0<p<1$. An $up-smoothsample$ $\mathrm{\Gamma }$ is a sample such that ${\mathrm{\Gamma }}_{i+1}-{\mathrm{\Gamma }}_i\le 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 $|{\mathrm{\Gamma }}_{i+1}-{\mathrm{\Gamma }}_i|\le 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,\dots ,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\ge 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\le f(v)\le 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}^{\prime }(G)$. Any simple graph $G$ has an $f$-edge covered chromatic index equal to ${\delta }_f$ or ${\delta }_f–1$, where ${\delta }_f=min\{\lfloor \frac{d(v)}{f(v)}\rfloor :v\in V(G)\}$. Let $G$ be a connected and not complete graph with ${\chi }_{fc}^{\prime }={\delta }_f–1$. If for each $u,v\in V$ and $e=uv\notin E$, we have ${\chi }_{fc}^{\prime }(G+e)>{\chi }_{fc}^{\prime }(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)\le {\delta }_f(f(w)+1)–2$ such that $w$ is adjacent to at least $max\{d(w)–{\delta }_{f}f(w)+1,(f(w)+2)d(w)–{\delta }_f(f(w)+1{)}^2+f(w)+3\}$ 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.