A set $S$ of vertices in a graph $G$ is a total dominating set of $G$ if every vertex of $G$ is adjacent to some vertex in $S$. The minimum cardinality of a total dominating set of $G$ is the total domination number of $G$. We study graphs having the same total domination number as their complements. In particular, we characterize the cubic graphs having this property. Also, we characterize such graphs with total domination numbers equal to two or three, and we determine properties of the ones with larger total domination numbers.

In 1991 Gnanajothi conjectured: Each tree is odd-graceful. In this paper, we define the edge-ordered odd-graceful labeling of trees and show the odd-gracefulness of all symmetric trees.

A method is suggested for the construction of quadrangulations of the closed orientable surface with given genus $g$ and either (1) with a given chromatic number or (2) with a given order allowed by the genus $g$. In particular, N. Hartshfield and G. Ringel’s results [J. Comb. Theory, Ser. B 46 (1989), 84-95] are generalized by way of generating minimal quadrangulations of infinitely many other genera.

For integers $s,t\ge 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, the lower bound for the Ramsey number $R(7,9)$ is improved from $241$ to $242$. The new bound is obtained by searching the maximum common induced subgraph between two graphs with a depth variable local search technique.

In this paper, we give an alternative and more intuitive proof to one of two classic inequalities given by Diaconis and Graham in 1977. The inequality involves three metrics on the symmetric group, i.e., the set of all permutations of the first $n$ positive integers. Our technique for the proof of the inequality allows us to resolve an open problem posed in that paper: When does equality hold? It also allows us to estimate how often equality holds. In addition, our technique can sometimes be applied for the proof of other inequalities between metrics or pseudo-metrics on the symmetric group.

Pooling designs are standard experimental tools in many biotechnical applications. In this paper, we construct a family of error-correcting pooling designs with the incidence matrix of two types of subspaces of singular linear space over finite fields, and exhibit their disjunct properties.

Let $S$ be an orthogonal polygon in the plane, bounded by a simple closed curve, and let $R$ be the smallest rectangular region containing $S$. Assume that $S$ is star-shaped via staircase paths. For every point $p$ in ${\mathbb{R}}^2\setminus (\text{int}S)$, there is a corresponding point $q$ in $\text{bdry}S$ such that $p$ lies in a maximal staircase convex cone $C_q$ at $q$ in ${\mathbb{R}}^2\setminus (\text{int}S)$. Furthermore, point $q$ may be selected to satisfy these requirements:

1. If $p\in {\mathbb{R}}^2\setminus (\text{int}R)$, then $q$ is an endpoint of an extreme edge of $S$.
2. If $p\in (\text{int}R)\setminus (\text{int}S)$, then $q$ is a point of local nonconvexity of $S$ and $C_q$ is unique. Moreover, there is a neighborhood $N$ of $q$ such that, for $s$ in $(\text{bdry}S)\cap N$ and for $C_s$ any staircase cone at $s$ in ${\mathbb{R}}^2\setminus (\text{int}S)$, $C_s\subseteq C_q$.

Thus we obtain a finite family of staircase convex cones whose union is ${\mathbb{R}}^2\setminus (\text{int}S)$.

If there are integers $k$ and $\lambda \ne 0$ such that a total labeling $f$ of a connected graph $G=(V,E)$ from $V\cup E$ to $\{1,2,\dots ,|V|+|E|\}$ satisfies $f(x)\ne f(y)$ for distinct $x,y\in V\cup E$ and

$$f(u)+f(v)=k+\lambda f(uv)$$

for each edge $uv\in E$, then $f$ is called a $(k,\lambda )$-$magicallytotallabeling$ ($(k,\lambda )$-$mtl$ for short) of $G$. Several properties of $(k,\lambda )$-$mtls$ of graphs are shown. The sufficient and necessary connections between $(k,\lambda )$-\emph{mtls} and several known labelings (such as graceful, odd-graceful, felicitous, and $(b,d)$-edge antimagic total labelings) are given. Furthermore, every tree is proven to be a subgraph of a tree having super $(k,\lambda )$-$mtls$.

Let $G$ be a simple graph of order $n$, and let $k$ be a positive integer. A graph $G$ is fractional independent-set-deletable $k$-factor-critical (in short, fractional ID-$k$-factor-critical) if $G–I$ has a fractional $k$-factor for every independent set $I$ of $G$. In this paper, we obtain a sufficient condition for a graph $G$ to be fractional ID-$k$-factor-critical. Furthermore, it is shown that the result in this paper is best possible in some sense.

Calculations of the number of equivalence classes of Sudoku boards has to this point been done only with the aid of a computer, in part because of the unnecessarily large symmetry group used to form the classes. In particular, the relationship between relabeling symmetries and positional symmetries such as row/column swaps is complicated. In this paper, we focus first on the smaller Shidoku case and show first by computation and then by using connectivity properties of simple graphs that the usual symmetry group can in fact be reduced to various minimal subgroups that induce the same action. This is the first step in finding a similar reduction in the larger Sudoku case and for other variants of Sudoku.

Let $k$ be a positive integer, and let $G$ be a simple graph with vertex set $V(G)$. A function $f:V(G)\to \{\pm 1,\pm 2,\dots ,\pm k\}$ is called a signed $\{k\}$-dominating function if

$$\sum _{u\in N[v]}f(u)\ge k$$

for each vertex $v\in V(G)$.

The signed $\{1\}$-dominating function is the same as the ordinary signed domination. A set $\{f_1,f_2,\dots ,f_d\}$ of signed $\{k\}$-dominating functions on $G$ with the property that

$$\sum _{i=1}^d{f}_i(v)\le k$$

for each $v\in V(G)$, is called a $signed\{k\}-dominatingfamily$ (of functions) on $G$. The maximum number of functions in a signed $\{k\}$-dominating family on $G$ is the $signed\{k\}-domaticnumber$ of $G$, denoted by $d_{\{k\}S}(G)$. Note that $d_{\{1\}S}(G)$ is the classical signed domatic number $d_s(G)$.

In this paper, we initiate the study of signed $\{k\}$-domatic numbers in graphs, and we present some sharp upper bounds for $d_{\{k\}S}(G)$. In addition, we determine $d_{\{k\}S}(G)$ for several classes of graphs. Some of our results are extensions of known properties of the signed domatic number.

A graceful $n$-permutation is a graceful labeling of an $n$-vertex path $P_n$. In this paper, we improve the asymptotic lower bound on the number of such permutations from $\mathrm{\Omega }\left({\left(\frac{5}{3}\right)}^n\right)$ to $\mathrm{\Omega }\left({2.37}^n\right)$. This is a computer-assisted proof based on an effective algorithm that enumerates graceful $n$-permutations. Our algorithm is also presented in detail.

Let $K_{r+1}$ be the complete graph on $r+1$ vertices and let $\pi =(d_1,d_2,\dots ,d_n)$ be a non-increasing sequence of nonnegative integers. If $\pi$ has a realization containing $K_{r+1}$ as a subgraph, then $\pi$ is said to be potentially $K_{r+1}$-graphic. A.R. Rao obtained an Erdős-Gallai type criterion for $\pi$ to be potentially $K_{r+1}$-graphic. In this paper, we provide a simplification of this Erdős-Gallai type criterion. Additionally, we present the Fulkerson-Hoffman-McAndrew type criterion and the Hasselbarth type criterion for $\pi$ to be potentially $K_{r+1}$-graphic.

In this paper, we introduce several concepts related to fuzzy algebraic structures. We provide an example of a fuzzy binary operation and a fuzzy group. Additionally, we define a new fuzzy binary operation on a $\mathrm{\Gamma }$-ring $M$ and introduce a new fuzzy $\mathrm{\Gamma }$-ring. We also present homomorphism theorems between two fuzzy $\mathrm{\Gamma }$-rings and investigate some related properties.

Let $R$ be a commutative ring and $Z(R)$ be its set of all zero-divisors. The \emph{total graph} of $R$, denoted by $T_{\mathrm{\Gamma }}(R)$, is the undirected graph with vertex set $R$, where two distinct vertices $x$ and $y$ are adjacent if and only if $x+y\in Z(R)$.

In this paper, we obtain a lower bound as well as an upper bound for the domination number of $T_{\mathrm{\Gamma }}(R)$. Further, we prove that the upper bound for the domination number of $T_{\mathrm{\Gamma }}(R)$ is attained in the case of an Artin ring $R$. Having established this, we identify certain classes of rings for which the domination number of the total graph equals this upper bound.

In view of these results, we conjecture that the domination number of $T_{\mathrm{\Gamma }}(R)$ is always equal to this upper bound. We also derive certain other domination parameters for $T_{\mathrm{\Gamma }}(R)$ under the assumption that the conjecture is true.

For given graphs $H_1$ and $H_2$, the $Ramseynumber$ $R(H_1,H_2)$ is the smallest positive integer $n$ such that if we arbitrarily color the edges of the complete graph $K_n$ with two colors, 1 (red) and 2 (blue), then there is a monochromatic copy of $H_1$ colored with 1 or $H_2$ colored with 2.

We show that if $n$ is even, $q=\lceil \sqrt{n}\rceil$ is odd, and $s=n–(q-1{)}^2\le \frac{q}{2}$, then $R(K_{2,2},K_{2,n})\le n+2q–1$, where $K_{n,m}$ are complete bipartite graphs. This bound provides the exact value of $R(K_{2,2},K_{2,18})=27$. Moreover, we show that $R(K_{2,2},K_{2,14})=22$ and $R(K_{2,2},K_{2,15})=24$.

A $red-bluecoloring$ of a graph $G$ is an edge coloring of $G$ in which every edge is colored red or blue. For a connected graph $H$ of size at least 2, a $colorframe$ $F$ of $H$ is obtained from a red-blue coloring of $H$ having at least one edge of each color and in which a blue edge is designated as the root edge.

An $F$-coloring of a graph $G$ is a red-blue coloring of $G$ in which every blue edge of $G$ is the root edge of a copy of $F$ in $G$, and the $F$-$chromaticindex$ of $G$ is the minimum number of red edges in an $F$-coloring of $G$. An $F$-coloring of $G$ is $minimal$ if whenever any red edge of $G$ is changed to blue, then the resulting red-blue coloring of $G$ is not an $F$-coloring of $G$. The maximum number of red edges in a minimal $F$-coloring of $G$ is the $upperF-chromaticindex$ of $G$.

In this paper, we investigate $F$-colorings and $F$-chromatic indexes of graphs for all color frames $F$ of paths of orders 3 and 4.

A set of vertices $S$ in a graph $G$ is a dominating set if any vertex of $G–S$ is adjacent to some vertex in $S$. The domination number, $\gamma (G)$, of $G$ is the minimum cardinality of a dominating set of $G$.

The subdivision of an edge $uv$ is the operation of replacing $uv$ with a path $uwv$ through a new vertex $w$. A graph $G$ is domination critical upon edge subdivision if the domination number increases by subdivision of any edge.

In this paper, we study domination critical graphs upon edge subdivision. We present several properties and bounds for these graphs and then give a constructive characterization of domination critical trees upon edge subdivision.

Let $G$ be a graph of order $n$. The $bindingnumber$ of $G$ is defined as

$$\text{bind}(G):=min\{\frac{|N_G(X)|}{|X|}\mid \mathrm{\varnothing }\ne X\subseteq V(G)\text{ and }{N}_G(X)\ne V(G)\}.$$

A $(g,f)$-factor is called a connected $(g,f)$-factor if it is connected. A $(g,f)$-factor $F$ is called a Hamilton $(g,f)$-factor if $F$ contains a Hamilton cycle. In this paper, several sufficient conditions related to binding number and minimum degree for graphs to have connected $(g,f+1)$-factors or Hamilton $(g,f)$-factors are given.

Define an edge $Q_1{Q}_2$ or a triangle $Q_1{Q}_2{Q}_3$ of a clique graph $K(G)$ to be weight-$k$ if $|Q_1\cap Q_2|\ge k$ or $|Q_1\cap Q_2\cap Q_3|\ge k$, respectively. A graph $G$ is shown to be strongly chordal if and only if, for every $k\ge 1$, every cycle of weight-$k$ edges in $K(G)$ either has a weight-$k$ chord or is a weight-$k$ triangle—this mimics the usual definition of chordal graphs. Similarly, trivially perfect graphs have a characterization that mimics a simple characterization of component-complete graphs.

We propose an original approach to the problem of rank-unimodality for Dyck lattices. It is based on a well-known recursive construction of Dyck paths originally developed in the context of the ECO methodology, which provides a partition of Dyck lattices into saturated chains. Even if we are not able to prove that Dyck lattices are rank-unimodal, we describe a family of polynomials (which constitutes a polynomial analog of ballot numbers) and a succession rule which appear to be useful in addressing such a problem. At the end of the paper, we also propose and begin a systematic investigation of the problem of unimodality of succession rules.

A Roman dominating function on a graph $G$ is a labeling $f:V(G)\to \{0,1,2\}$ such that every vertex with label $0$ has a neighbor with label $2$. The weight of a Roman dominating function is the value $f(V(G))=\sum _{u\in V(G)}f(u)$. The minimum weight of a Roman dominating function on a graph $G$ is called the Roman domination number, denoted by ${\gamma }_R(G)$. The Roman bondage number of a graph $G$ is the cardinality of a smallest set of edges whose removal results in a graph with Roman domination number greater than that of $G$.

In this paper, we initiate the study of the Roman fractional bondage number, and we present different bounds on Roman fractional bondage. In addition, we determine the Roman fractional bondage number of some classes of graphs.

We show that the principal results of the article “The metric dimension of graphs with pendant edges” [Journal of Combinatorial Mathematics and Combinatorial Computing, 65 (2008) 139-145] do not hold. In this paper, we correct the results and we solve two open problems described in the above-mentioned paper.

Using the definition of the representation number of a graph modulo integers given by Erdős and Evans, we establish the representation number of a complete graph minus a set of disjoint stars. The representation number of a graph $G$ is the smallest positive integer $n$ for which there is a labeling of every vertex of $G$ with a distinct element of $\{0,1,2,\dots ,n-1\}$ such that two vertices are adjacent if and only if the difference of their labels is relatively prime to $n$. We apply known results to a complete graph minus a set of stars to establish a lower bound for the representation number; then show a systematic labeling of the vertices producing a representation that attains that lower bound. Thus showing that for complete graphs minus a set of disjoint stars, the established lower bound of the representation number modulo $n$ is indeed the representation number of the graph. Since the representation modulo an integer for a complete graph minus disjoint stars is attained using the fewest number of primes allowed by the lower bound, it follows that the corresponding Prague dimension will be determined by the largest star removed from the complete graph.

Let $\lambda K_v$ be the complete multigraph of order $v$ and index $\lambda$, where any two distinct vertices $x$ and $y$ are joined exactly by $\lambda$ edges $\{x,y\}$. Let $G$ be a finite simple graph. A $G$-design of $\lambda K_v$, denoted by $(v,G,\lambda )$-GD, is a pair $(X,\mathcal{B})$, where $X$ is the vertex set of $K_v$, and $\mathcal{B}$ is a collection of subgraphs of $\lambda 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}$. There are four graphs which are a 6-circle with two pendant edges, denoted by $G_i$, $i=1,2,3,4$. In [9], we have solved the existence problems of $(v,G_i,1)$-GD. In this paper, we obtain the existence spectrum of $(v,G_i,\lambda )$-GD for any $\lambda >1$.

The decycling index of a digraph is the minimum number of arcs whose removal yields an acyclic digraph. The maximum arc decycling number ${\overline{\mathrm{\nabla }}}^{\prime }(m,n)$ is the maximum decycling index among all $m\times n$ bipartite tournaments. Recently, R.C. Vandell determined the numbers ${\overline{\mathrm{\nabla }}}^{\prime }(2,n)$, ${\overline{\mathrm{\nabla }}}^{\prime }(3,n)$, and ${\overline{\mathrm{\nabla }}}^{\prime }(4,n)$ for all positive integers $n$, as well as ${\overline{\mathrm{\nabla }}}^{\prime }(5,5)$. In this work, we use a computer program to obtain ${\overline{\mathrm{\nabla }}}^{\prime }(5,6)$, ${\overline{\mathrm{\nabla }}}^{\prime }(6,6)$, and ${\overline{\mathrm{\nabla }}}^{\prime }(5,7)$, as well as some results on ${\overline{\mathrm{\nabla }}}^{\prime }(6,7)$ and ${\overline{\mathrm{\nabla }}}^{\prime }(5,8)$. In particular, ${\overline{\mathrm{\nabla }}}^{\prime }(6,6)=10$, and this confirms a conjecture of Vandell.

Let $G=(V,E)$ be a graph. A function $f:V\to \{-1,1\}$ is called a signed dominating function on $G$ if $\sum _{u\in N_G[v]}f(u)\ge 1$ for each $v\in V$, where $N_G[v]$ is the closed neighborhood of $v$. A set $\{f_1,f_2,\dots ,f_d\}$ of signed dominating functions on $G$ is called a signed dominating family (of functions) on $G$ if $\sum _{i=1}^d{f}_i(v)\le 1$ for each $v\in V$. The signed domatic number of $G$ is the maximum number of functions in a signed dominating family on $G$. The signed total domatic number is defined similarly, by replacing the closed neighborhood $N_G[v]$ with the open neighborhood $N_G(v)$ in the definition. In this paper, we prove that the problems of computing the signed domatic number and the signed total domatic number of a given graph are both NP-hard, even if the graph has bounded maximum degree. To the best of our knowledge, these are the first NP-hardness results for these two variants of the domatic number.