We will discuss the vertex-distinguishing I-total colorings and vertex-distinguishing VI-total colorings of three types of graphs: $S_m\vee F_n,S_m\vee W_n$ and $F_n\vee W_n$ in this paper. The optimal vertex-distinguishing I (resp. VI)-total colorings of these join graphs are given by the method of constructing colorings according to their structural properties and the vertex-distinguishing I (resp. VI)-total chromatic numbers of them are determined.

A graph is called set-reconstructible if it is determined uniquely (up to isomorphism) by the set of its vertex-deleted subgraphs. The maximal subgraph of a graph $H$ that is a tree rooted at a vertex $u$ of $H$ is the limb at $u$. It is shown that two families ${\mathcal{F}}_1$ and ${\mathcal{F}}_2$ of nearly acyclic graphs are set-reconstructible. The family ${\mathcal{F}}_1$ consists of all connected cyclic graphs $G$ with no end vertex such that there is a vertex lying on all the cycles in $G$ and there is a cycle passing through at least one vertex of every cycle in $G$. The family ${\mathcal{F}}_2$ consists of all connected cyclic graphs $H$ with end vertices such that there are exactly two vertices lying on all the cycles in $H$ and there is a cycle with no limbs at its vertices.

In this paper, we determine the second largest number of maximal independent sets and characterize those extremal graphs achieving these values among all twinkle graphs.

In this paper, we characterize the set of spanning trees of $G_{n,r}^1$ (a simple connected graph consisting of $n$ edges, containing exactly one 1-edge-connected chain of $r$ cycles $C_r^1$ and $G_{n,r}^1\setminus C_r^1$ is a forest). We compute the Hilbert series of the face ring $k[{\mathrm{\Delta }}_s(G_{n,r}^1)]$ for the spanning simplicial complex ${\mathrm{\Delta }}_s(G_{n,r}^1)$. Also, we characterize associated primes of the facet ideal $I_F({\mathrm{\Delta }}_s(G_{n,r}^1))$. Furthermore, we prove that the face ring $k[{\mathrm{\Delta }}_s(G_{n,r}^1)]$ is Cohen-Macaulay.

Let $G$ be a simple and finite graph. A graph is said to be decomposed into subgraphs $H_1$ and $H_2$ which is denoted by $G=H_1\oplus H_2,$ if $G$ is the edge-disjoint union of $H_1$ and $H_2$. If $G=H_1\oplus H_2\oplus \cdots \oplus H_k,$where $H_1,H_2,\dots ,H_k$ are all isomorphic to $H$, then $G$ is said to be $H$-decomposable. Furthermore, if $H$ is a cycle of length $m$, then we say that $G$ is $C_m$-decomposable and this can be written as $C_m\mid G$. Where $G\times H$ denotes the tensor product of graphs $G$ and $H$, in this paper, we prove that the necessary conditions for the existence of $C_6$-decomposition of $K_m\times K_n$ are sufficient. Using these conditions, it can be shown that every even regular complete multipartite graph $G$ is $C_6$-decomposable if the number of edges of $G$ is divisible by 6.

Constructions of the smallest known trivalent graph for girths 17, 18, and 20 are given. All three graphs are voltage graphs. Their orders are 2176, 2560, and 5376, respectively, improving the previous values of 2408, 2640, and 6048.

A signed total Italian dominating function (STIDF) of a graph $G$ with vertex set $V(G)$ is defined as a function $f:V(G)\to \{-1,1,2\}$ having the property that (i) $\sum _{x\in N(v)}f(x)\ge 1$ for each $v\in V(G)$, where $N(v)$ is the neighborhood of $v$, and (ii) every vertex $u$ for which $f(u)=-1$ is adjacent to a vertex $v$ for which $f(v)=2$ or adjacent to two vertices $w$ and $z$ with $f(w)=f(z)=1$. The weight of an STIDF is the sum of its function values over all vertices. The \textit{signed total Italian domination number} of $G$, denoted by ${\gamma }_{stI}(G)$, is the minimum weight of an STIDF in $G$. We initiate the study of the signed total Italian domination number, and we present different sharp bounds on ${\gamma }_{stI}(G)$. In addition, we determine the signed total Italian domination number of some classes of graphs.

One may generalize integer compositions by replacing positive integers with elements from an additive group, giving the broader concept of compositions over a group. In this note, we give some simple bijections between compositions over a finite group. It follows from these bijections that the number of compositions of a nonzero group element $g$ is independent of $g$. As a result, we derive a simple expression for the number of compositions of any given group element. This extends an earlier result for abelian groups which was obtained using generating functions and a multivariate multisection formula.

An acyclic ordering of a directed acyclic graph (DAG) $G$ is a sequence $\alpha$ of the vertices of $G$ with the property that if $i<j$, then there is a path in $G$ from $\alpha (i)$ to $\alpha (j)$. In this paper, we explore the problem of finding the number of possible acyclic orderings of a general DAG. The main result is a method for reducing a general DAG to a simpler one when counting the number of acyclic orderings. Along the way, we develop a formula for quickly obtaining this count when a DAG is a tree.

The diagnosability of a multiprocessor system is one important study topic. In 2016, Zhang et al. proposed a new measure for fault diagnosis of the system, namely, the $g$-extra diagnosability, which restrains that every fault-free component has at least $(g+1)$ fault-free nodes. As a favorable topology structure of interconnection networks, the $n$-dimensional alternating group graph $A{G}_n$ has many good properties. In this paper, we prove that the 3-extra diagnosability of $A{G}_n$ is $8n–25$ for $n\ge 5$ under the PMC model and for $n\ge 7$ MM* model.

M. Klešc et al. characterized graphs $G_1$ and $G_2$ for which the crossing number of their Cartesian product $G_1\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{G}_2$ equals one or two. In this paper, their results are extended by giving the necessary and sufficient conditions for all pairs of graphs $G_1$ and $G_2$ for which the crossing number of their Cartesian product $G_1\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{G}_2$ equals three, if one of the graphs $G_1$ and $G_2$ is a cycle.

In this paper we study relations between connected and weakly convex domination numbers. We show that in general the difference between these numbers can be arbitrarily large and we focus on the graphs for which a weakly convex domination number equals a connected domination number. We also study the influence of the edge removing on the weakly convex domination number, in particular we prove that the weakly convex domination number is an interpolating function.

Denote by $p_m$ the $m$-th prime number ($p_1=2$, $p_2=3$, $p_3=5$, $p_4=7$, \dots). Let $T$ be a rooted tree with branches $T_1,T_2,\dots ,T_r$. The Matula number $M(T)$ of $T$ is $p_{M(T_1)}\cdot p_{M(T_2)}\cdots p_{M(T_r)}$, starting with $M(K_1)=1$. This number was put forward half a century ago by the American mathematician David Matula. In this paper, we prove that the star (consisting of a root and leaves attached to it) and the binary caterpillar (a binary tree whose internal vertices form a path starting at the root) have the smallest and greatest Matula number, respectively, over all topological trees (rooted trees without vertices of outdegree 1) with a prescribed number of leaves – the extreme values are also derived.

Rotation distance between rooted binary trees is the minimum number of simple rotations needed to transform one tree into the other. Computing the rotation distance between a pair of rooted trees can be quickly reduced in cases where there is a common edge between the trees, or where a single rotation introduces a common edge. Tree pairs which do not have such a reduction are difficult tree pairs, where there is no generally known first step. Here, we describe efforts to count and estimate the number of such difficult tree pairs, and find that the fraction decreases exponentially fast toward zero. We also describe how knowing the number of distinct instances of the rotation distance problem is a helpful factor in making the computations more feasible.

In this paper, we characterize the set of spanning trees of $G_{n,r}^1$ (a simple connected graph consisting of $n$ edges, containing exactly one \textit{1-edge-connected chain} of $r$ cycles $C_r^1$ and $G_{n,r}^1$, where $C_r^1$ is a \textit{forest}). We compute the Hilbert series of the face ring $k[{\mathrm{\Delta }}_s(G_{n,r}^1)]$ for the spanning simplicial complex ${\mathrm{\Delta }}_s(G_{n,r}^1)$. Also, we characterize associated primes of the facet ideal $I_F({\mathrm{\Delta }}_s(G_{n,r}^1))$. Furthermore, we prove that the face ring $k[{\mathrm{\Delta }}_s(G_{n,r}^1)]$ is Cohen-Macaulay.

Unlike undirected graphs where the concept of Roman domination has been studied very extensively over the past 15 years, Roman domination remains little studied in digraphs. However, the published works are quite varied and deal with different aspects of Roman domination, including for example, Roman bondage, Roman reinforcement, Roman dominating family of functions and the signed version of some Roman dominating functions. In this survey, we will explore some Roman domination related results on digraphs, some of which are extensions of well-known properties of the Roman domination parameters of undirected graphs.

Let $K_{g_1,g_2,\dots ,g_n}$ be a complete $n$-partite graph with partite sets of sizes $g_i$ for $1\le i\le n$. A complete $n$-partite is balanced if each partite set has $g$ vertices. In this paper, we will solve the problem of finding a maximum packing of the balanced complete $n$-partite graph, $n$ even, with edge-disjoint 5-cycles when the leave is a 1-factor.

A double Italian dominating function on a graph $G$ with vertex set $V(G)$ is defined as a function $f:V(G)\to \{0,1,2,3\}$ such that each vertex $u\in V(G)$ with $f(u)\in \{0,1\}$ has the property that $\sum _{x\in N[u]}f(x)\ge 3$, where $N[u]$ is the closed neighborhood of $u$. A set $\{f_1,f_2,\dots ,f_d\}$ of distinct double Italian dominating functions on $G$ with the property that $\sum _{i=1}^d{f}_i(v)\le 3$ for each $v\in V(G)$ is called a \textit{double Italian dominating family} (of functions) on $G$. The maximum number of functions in a double Italian dominating family on $G$ is the double Italian domatic number of $G$, denoted by $d{d}_I(G)$. We initiate the study of the double Italian domatic number, and we present different sharp bounds on $d{d}_I(G)$. In addition, we determine the double Italian domatic number of some classes of graphs.

We define the push statistic on permutations and multipermutations and use this to obtain various results measuring the degree to which an arbitrary permutation deviates from sorted order. We study the distribution on permutations for the statistic recording the length of the longest push and derive an explicit expression for its first moment and generating function. Several auxiliary concepts are also investigated. These include the number of cells that are not pushed; the number of cells that coincide before and after pushing (i.e., the fixed cells of a permutation); and finally the number of groups of adjacent columns of the same height that must be reordered at some point during the pushing process.

Let $\mathcal{K}$ be a family of sets in ${\mathbb{R}}^d$. For each countable subfamily $\{K_m:m\ge 1\}$ of $\mathcal{K}$, assume that $\bigcap \{K_m:m\ge 1\}$ is consistent relative to staircase paths and starshaped via staircase paths, with a staircase kernel that contains a convex set of dimension $d$. Then $\bigcap \{K:K\in \mathcal{K}\}$ has these properties as well. For $n$ fixed, $n\ge 1$, an analogous result holds for sets starshaped via staircase $n$-paths.

We introduce a new bivariate polynomial which we call the defensive alliance polynomial and denote it by $da(G;x,y)$. It is a generalization of the alliance polynomial [Carballosa et al., 2014] and the strong alliance polynomial [Carballosa et al., 2016]. We show the relation between $da(G;x,y)$ and the alliance, the strong alliance, and the induced connected subgraph [Tittmann et al., 2011] polynomials. Then, we investigate information encoded in $da(G;x,y)$ about $G$. We discuss the defensive alliance polynomial for the path graphs, the cycle graphs, the star graphs, the double star graphs, the complete graphs, the complete bipartite graphs, the regular graphs, the wheel graphs, the open wheel graphs, the friendship graphs, the triangular book graphs, and the quadrilateral book graphs. Also, we prove that the above classes of graphs are characterized by its defensive alliance polynomial. A relation between induced subgraphs with order three and both subgraphs with order three and size three and two respectively, is proved to characterize the complete bipartite graphs. Finally, we present the defensive alliance polynomial of the graph formed by attaching a vertex to a complete graph. We show two pairs of graphs which are not characterized by the alliance polynomial but characterized by the defensive alliance polynomial.

A cancellable number (CN) is a fraction in which a decimal digit can be removed (“canceled”) in the numerator and denominator without changing the value of the number; examples include $\frac{64}{16}$ where the 6 can be canceled and $\frac{98}{49}$ where the 9 can be canceled. We present a few limit theorems and provide several generalizations.

Linear codes from neighborhood designs of strongly regular graphs such as triangular, lattice, and Paley graphs have been extensively studied over the past decade. Most of these families of graphs are line graphs of a much larger class known as circulant graphs, ${\mathrm{\Gamma }}_n(S)$. In this article, we extend earlier results to obtain properties and parameters of binary codes $C_n(S)$ from neighborhood designs of line graphs of circulant graphs.

Necessary conditions for the existence of a $3$-GDD$(n,3,k;{\lambda }_1,{\lambda }_2)$ are obtained along with some non-existence results. We also prove that these necessary conditions are sufficient for the existence of a $3$-GDD$(n,3,4;{\lambda }_1,{\lambda }_2)$ for $n$ even.

The paired domination subdivision number ${\text{sd}}_{pr}(G)$ of a graph $G$ is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of $G$. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason, we define the \textit{paired domination multisubdivision number} of a nonempty graph $G$, denoted by ${\text{msd}}_{pr}(G)$, as the minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to increase the paired domination number of $G$. We show that ${\text{msd}}_{pr}(G)\le 4$ for any graph $G$ with at least one edge. We also determine paired domination multisubdivision numbers for some classes of graphs. Moreover, we give a constructive characterization of all trees with paired domination multisubdivision number equal to 4.

Consider the multigraph obtained by adding a double edge to $K_4–e$. Now, let $D$ be a directed graph obtained by orientating the edges of that multigraph. We establish necessary and sufficient conditions on $n$ for the existence of a $(K_n^{\ast },D)$-design for four such orientations.

Working on general hypergraphs requires to properly redefine the concept of adjacency in a way that it captures the information of the hyperedges independently of their size. Coming to represent this information in a tensor imposes to go through a uniformisation process of the hypergraph. Hypergraphs limit the way of achieving it as redundancy is not permitted. Hence, our introduction of hb-graphs, families of multisets on a common universe corresponding to the vertex set, that we present in details in this article, allowing us to have a construction of adequate adjacency tensor that is interpretable in term of $m$-uniformisation of a general hb-graph. As hypergraphs appear as particular hb-graphs, we deduce two new ($e$)-adjacency tensors for general hypergraphs. We conclude this article by giving some first results on hypergraph spectral analysis of these tensors and a comparison with the existing tensors for general hypergraphs, before making a final choice.

The paper proposes techniques which provide closed-form solutions for special simultaneous systems of two and three linear recurrences. These systems are characterized by particular restrictions on their coefficients. We discuss the application of these systems to some algorithmic problems associated with the relationship between algebraic expressions and graphs. Using decomposition methods described in the paper, we generate the simultaneous recurrences for graph expression lengths and solve them with the proposed approach.

For a given graph $G$, a variation of its line graph is the 3-xline graph, where two 3-paths $P$ and $Q$ are adjacent in $G$ if $V(P)\cap V(Q)=\{v\}$ when $v$ is the interior vertex of both $P$ and $Q$. The vertices of the 3-xline graph $X{L}_3(G)$ correspond to the 3-paths in $G$, and two distinct vertices of the 3-xline graph are adjacent if and only if they are adjacent 3-paths in $G$. In this paper, we study 3-xline graphs for several classes of graphs, and show that for a connected graph $G$, the 3-xline graph is never isomorphic to $G$ and is connected only when $G$ is the star $K_{1,n}$ for $n=2$ or $n\ge 5$. We also investigate cycles in 3-xline graphs and characterize those graphs $G$ where $X{L}_3(G)$ is Eulerian.

An $L(h,k)$ labeling of a graph $G$ is an integer labeling of the vertices where the labels of adjacent vertices differ by at least $h$, and the labels of vertices that are at distance two from each other differ by at least $k$. The span of an $L(h,k)$ labeling $f$ on a graph $G$ is the largest label minus the smallest label under $f$. The $L(h,k)$ span of a graph $G$, denoted ${\lambda }_{h,k}(G)$, is the minimum span of all $L(h,k)$ labelings of $G$.

In this paper, we use standard graph labeling techniques to prove that each tri-cyclic graph with eight edges decomposes the complete graph $K_n$ if and only if $n\equiv 0,1(\mathrm{mod}16)$. We apply $\rho$-tripartite labelings and 1-rotational $\rho$-tripartite labelings.

We introduce a variation of $\sigma$-labeling to prove that every disconnected unicyclic bipartite graph with eight edges decomposes the complete graph $K_n$ whenever the necessary conditions are satisfied. We combine this result with known results in the connected case to prove that every unicyclic bipartite graph with eight edges other than $C_8$ decomposes $K_n$ if and only if $n\equiv 0,1(\mathrm{mod}16)$ and $n>16$.

Let $G$ be a tripartite unicyclic graph with eight edges that either (i) contains a triangle or heptagon, or (ii) contains a pentagon and is disconnected. We prove that $G$ decomposes the complete graph $K_n$ whenever the necessary conditions are satisfied. We combine this result with other known results to prove that every unicyclic graph with eight edges other than $C_8$ decomposes $K_n$ if and only if $n\equiv 0,1(\mathrm{mod}16)$.

For a positive integer $k$, let $P^{\ast }([k])$ denote the set of nonempty subsets of $[k]=\{1,2,\dots ,k\}$. For a graph $G$ without isolated vertices, let $c:E(G)\to P^{\ast }([k])$ be an edge coloring of $G$ where adjacent edges may be colored the same. The induced vertex coloring $c^{\prime }:V(G)\to P^{\ast }([k])$ is defined by $c^{\prime }(v)=\bigcap _{e\in E_v}c(e)$, where $E_v$ is the set of edges incident with $v$. If $c^{\prime }$ is a proper vertex coloring of $G$, then $c$ is called a regal $k$-edge coloring of $G$. The minimum positive integer $k$ for which a graph $G$ has a regal $k$-edge coloring is the regal index of $G$. If $c^{\prime }$ is vertex-distinguishing, then $c$ is a strong regal $k$-edge coloring of $G$. The minimum positive integer $k$ for which a graph $G$ has a strong regal $k$-edge coloring is the strong regal index of $G$. The regal index (and, consequently, the strong regal index) is determined for each complete graph and for each complete multipartite graph. Sharp bounds for regal indexes and strong regal indexes of connected graphs are established. Strong regal indexes are also determined for several classes of trees. Other results and problems are also presented.

A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $T$ with $n$ edges, it is conjectured that there exists a labeling $f:V(T)\to \{0,1,\dots ,n\}$ such that the set of induced edge labels $\{|f(u)–f(v)|:\{u,v\}\in E(T)\}$ is exactly $\{1,2,\dots ,n\}$. We extend this concept to allow for multigraphs with edge multiplicity at most 2. A 2-fold graceful labeling of a graph (or multigraph) $G$ with $n$ edges is a one-to-one function $f:V(G)\to \{0,1,\dots ,n\}$ such that the multiset of induced edge labels is comprised of two copies of each element in $\{1,2,\dots ,\lfloor n/2\rfloor \}$, and if $n$ is odd, one copy of $\{\lfloor n/2\rfloor \}$. When $n$ is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $n\ne 1\mathrm{mod}4$, and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is 2-fold graceful.

We develop an ordering function on the class of tournament digraphs (complete antisymmetric digraphs) that is based on the Rényi $\alpha$-entropy. This ordering function partitions tournaments on $n$ vertices into equivalence classes that are approximately sorted from transitive (the arc relation is transitive — the score sequence is $(0,1,2,\dots ,n-1)$) to regular (score sequence like $(\frac{n-1}{2},\dots ,\frac{n-1}{2})$). However, the diversity among regular tournaments is significant; for example, there are 1,123 regular tournaments on 11 vertices and 1,495,297 regular tournaments on 13 vertices up to isomorphism, which is captured to an extent.

Given a graph $G$, we are interested in finding disjoint paths for a given set of distinct pairs of vertices. In 2017, we formally defined a new parameter, the pansophy of $G$, in the context of the disjoint path problem. In this paper, we develop an algorithm for computing the pansophy of graphs and illustrate the algorithm on graphs where the pansophy is already known. We close with future research directions.

Let $G$ be one of the two multigraphs obtained from $K_4-e$ by replacing two edges with a double-edge while maintaining a minimum degree of 2. We find necessary and sufficient conditions on $n$ and $\lambda$ for the existence of a $G$-decomposition of $K_n$.

Let $m$ and $n$ be positive integers, and let $R=(r_1,\dots ,r_m)$ and $S=(s_1,\dots ,s_n)$ be non-negative integral vectors. Let $\mathcal{A}(R,S)$ be the set of all $m\times n$ $(0,1)$-matrices with row sum vector $R$ and column vector $S$. Let $R$ and $S$ be non-increasing, and let $F(R,S)$ be the $m\times n$ $(0,1)$-matrix where for each $i$, the $i^{\text{th}}$ row of $F(R,S)$ consists of $r_i$ 1’s followed by $n–r_i$ 0’s, called Ferrers matrices. The discrepancy of an $m\times n$ $(0,1)$-matrix $A$, $\text{disc}(A)$, is the number of positions in which $F(R,S)$ has a 1 and $A$ has a 0. In this paper we investigate linear operators mapping $m\times n$ matrices over the binary Boolean semiring to itself that preserve sets related to the discrepancy. In particular we characterize linear operators that preserve both the set of Ferrers matrices and the set of matrices of discrepancy one.

The line graph $L(G)$ of a nonempty graph $G$ has the set of edges in $G$ as its vertex set where two vertices of $L(G)$ are adjacent if the corresponding edges of $G$ are adjacent. Let $k>2$ be an integer and let $G$ be a graph containing k-paths (paths of order $k$). The k-path graph $P_k(G)$ of $G$ has the set of k-paths of $G$ as its vertex set where two distinct vertices of $P_k(G)$ are adjacent if the corresponding k-paths of $G$ have a $(k-1)$-path in common. Thus, $P_2(G)=L(G)$ and $P_3(G)=L(L(G))$. Hence, the k-path graph $P_k(G)$ of a graph $G$ is a generalization of the line graph $L(G)$. Let $G$ be a connected graph of order $n>3$ and let $k$ be an integer with $2<k2$, then $P_3(T)$ is $k$-tree-connected. This conjecture was verified for $k=2,3$. In this work, we show that if $T$ is a tree of order at least 6 containing no vertices of degree 2, 3, 4, or 5, then $P_3(T)$ is 4-tree-connected and so verify the conjecture for the case when $k=4$.