For natural numbers $n$ and $k$, where $n>2k$, a generalized Petersen graph $P(n,k)$ is obtained by letting its vertex set be $\{u_1,u_2,\dots ,u_n\}\cup \{v_1,v_2,\dots ,v_n\}$ and its edge set be the union of $\{u_i{u}_{i+1},u_i{v}_i,v_i{v}_{i+k}\}$ over $1\le i\le n$, where subscripts are reduced modulo $n$. In this paper, an integer programming formulation for Roman domination is established, which is used to give upper bounds for the Roman domination numbers of the generalized Petersen graphs $P(n,3)$ and $P(n,4)$. Together with the dynamic algorithm, we determine the Roman domination number of the generalized Petersen graph $P(n,3)$ for $n\ge 5$.

In this paper, we introduce the zero-divisor graph $\mathrm{\Gamma }(L)$ of a meet-semilattice $L$ with 0. It is shown that $\mathrm{\Gamma }(L)$ is connected with $\text{diam}(\mathrm{\Gamma }(L))\le 3$ and if $\mathrm{\Gamma }(L)$ contains a cycle, then the core $K$ of $\mathrm{\Gamma }(L)$ is a union of 3-cycles and 4-cycles.

A unit distance graph is a finite simple graph which may be drawn on the plane so that its vertices are represented by distinct points and the edges are represented by closed line segments of unit length. In this paper, we show that the only primitive strongly regular unit distance graphs are $(i)$ the pentagon, $(ii)$ $K_3\times K_3$, $(iii)$ the Petersen graph, and $(iv)$ possibly the Hoffman-Singleton graph.

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 symplectic spaces over finite fields.

In $1969$, Dewdney introduced the set $\mathrm{\Gamma }$ of $primalgraphs$, characterized by the following two properties: every finite, simple graph $G$ is the union of non-isomorphic, edge-disjoint subgraphs of $G$ so that each of the subgraphs is in $\mathrm{\Gamma }$; and, if $G$ is in $\mathrm{\Gamma }$, then the only such union consists of $G$ itself. In the period around 1990, several works concerning the determination of the graphs in $\mathrm{\Gamma }$ were published and one Ph.D. thesis written. However, the classification of the members of $\mathrm{\Gamma }$ remains elusive. The main point of this work is to simplify and unify some of the principal results of Preen’s Ph.D. thesis that generalize earlier results about primal graphs with maximum degree $2$.

In order to characterize convex polyhedra with regular polygonal faces by a minimal number of parameters, we first introduce some new parameters, then we analyze a table of their values to see how well different sets of parameters tell these solids apart, and finally we present their characterization by four parameters.

In this paper, we show a short proof of the $q$-binomial theorem by Schützenberger’s identity with $q$-commuting variables.

A non-empty $r$-element subset $A$ of an $n$-element set $X_n$, and a partition $\pi$ of $X_n$, are said to be orthogonal if every class of $\pi$ meets $A$ in exactly one element. A partition type is determined by the number of classes of each distinct size of the partition. The Johnson graph $J(n,r)$ is the graph whose vertices are the $r$-element subsets of $X_n$, with two sets being adjacent if they intersect in $r-1$ elements. A partition of a given type $\tau$ is said to be a $\tau$-label for an edge $AB$ in $J(n,r)$ if the sets $A$ and $B$ are orthogonal to the partition. A cycle $\mathcal{H}$ in the graph $J(n,r)$ is said to be $\tau$-labeled if for every edge of $\mathcal{H}$, there exists a $\tau$-label, and the $\tau$-labels associated with distinct edges are distinct. Labeled Hamiltonian cycles are used to produce minimal generating sets for transformation semigroups. We identify a large class of partition types $\tau$ with a non-zero gap for which every Hamiltonian cycle in the graph $J(n,r)$ can be $\tau$-labeled, showing, for example, that this class includes all the partition types with at least one class of size larger than 3 or at least three classes of size 3.

Let $G$ be a graph, and $k$ 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, it is proved that if $\kappa (G)\ge max\{\frac{k^2+6k+1}{2},\frac{(k^2+6k+1)\alpha (G)}{4k}\}$, then $G$ is fractional ID-$k$-factor-critical.

In this paper, we constructed two multireceiver authentication codes from singular symplectic geometry over finite fields. Under the assumption that the probability distribution on the source states and sender’s key space is uniform, the parameters and success probabilities of different types of deceptions are also computed.

An oriented coloring of a directed graph is a vertex coloring in which no two adjacent vertices belong to the same color class and all of the arcs between any two color classes have the same direction. Injective oriented colorings are oriented colorings that satisfy the extra condition that no two in-neighbors of a vertex receive the same color. The oriented chromatic number of an unoriented graph is the maximum oriented chromatic number over all possible orientations. Similarly, the injective oriented chromatic number of an unoriented graph is the maximum injective oriented chromatic number over all possible orientations. The main results obtained in this paper are bounds on the injective oriented chromatic number of two-dimensional grid graphs.

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 $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 with seven vertices, seven edges, and one 5-cycle, 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 index $\lambda$.

The values of the Ramsey numbers $R(C_4,H)$, for any graph $H$ on 6 vertices, are shown in [3]. An erratum is corrected in [4,6], giving $R(C_4,K_{3,3})=11$.

In this paper, we correct three other errata of [3], proving that $R(C_4,K_1+(K_{2,3}–e))=9$, $R(C_4,\overline{K_3\cup P_3})=11$, and $R(C_4,\overline{2P_3})=11$, instead of 10.

We use dynamic programming to compute the domination number of the Cartesian product of two directed paths, ${\overrightarrow{P}}_m$ and ${\overrightarrow{P}}_n$, for $m\le 25$ and all $n$. This suggests that the domination number for $min(m,n)\ge 4$ is $\lfloor \frac{(m+1)(n+1)}{3}\rfloor –1$, which we then confirm by showing that this is both an upper and a lower bound on the domination number.

In 1975, Erdős proposed the problem of determining the maximal number of edges in a graph on $n$ vertices that contains no triangles or squares. In this paper, we consider a generalized version of the problem, i.e., what is the maximum size, $ex(n;t)$, of a graph of order $n$ and girth at least $t+1$ (containing no cycles of length less than $t+1$). The set of those extremal $C_t$-free graphs is denoted by $EX(n;t)$. We consider the problem on special types of graphs, such as pseudotrees, cacti, graphs lying in a square grid, Halin, generalized Halin, and planar graphs. We give the extremal cases, some constructions, and we use these results to obtain general lower bounds for the problem in the general case.

This paper develops the polyhedral approach to integer partitions. We consider the set of partitions of an integer $n$ as a polytope $P_n\subset {\mathbb{R}}^n$. Vertices of $P_n$ form the class of partitions that provide the first basis for the whole set of partitions of $n$. Moreover, we show that there exists a subclass of vertices, from which all others can be generated with the use of two combinatorial operations. The calculation demonstrates a considerable decrease in the cardinality of these classes of basic partitions as $n$ grows. We focus on the vertex enumeration problem for $P_n$. We prove that vertices of all partition polytopes form a partition ideal of the Andrews partition lattice. This allows us to construct vertices of $P_n$ by a lifting method, which requires examining only certain partitions of $n$. A criterion of whether a given partition is a convex combination of two others connects vertices with knapsack partitions, sum-free sets, Sidon sets, and Sidon multisets introduced in the paper. All but a few non-vertices for small $n$’s were recognized with its help. We also prove several easy-to-check necessary conditions for a partition to be a vertex.

Like the Coxeter graph becoming reattached into the Klein graph in [3], the Levi graphs of the $9_3$ and ${10}_3$ self-dual configurations, known as the Pappus and Desargues ($k$-transitive) graphs $\mathcal{P}$ and $\mathcal{D}$ (where $k=3$), also admit reattachments of the distance-($k–1$) graphs of half of their oriented shortest cycles via orientation assignments on their common ($k–1$)-arcs, concurrent for $\mathcal{P}$ and opposite for $\mathcal{D}$, now into 2 disjoint copies of their corresponding Menger graphs. Here, $\mathcal{P}$ is the unique cubic distance-transitive (or CDT) graph with the concurrent-reattachment behavior while $\mathcal{D}$ is one of $7$ CDT graphs with the opposite-reattachment behavior, including the Coxeter graph. Thus, $\mathcal{P}$ and $\mathcal{D}$ confront each other in these respects, obtained via $\mathcal{C}$-ultrahomogeneous graph techniques $[4,5]$ that allow us to characterize the obtained reattachment Menger graphs in the same terms.

Let $k$ be a positive integer and $G=(V,E)$ be a graph of minimum degree at least $k–1$. A function $f:V\to \{-1,1\}$ is called a $signedk-dominatingfunction$ of $G$ if $\sum _{u\in N_G[v]}f(u)\ge k$ for all $v\in V$. The $signedk-dominationnumber$ of $G$ is the minimum value of $\sum _{v\in V}f(v)$ taken over all signed $k$-dominating functions of $G$. The $signedtotalk-dominatingfunction$ and $signedtotalk-dominationnumber$ of $G$ can be similarly defined by changing the closed neighborhood $N_G[v]$ to the open neighborhood $N_G(v)$ in the definition. The upper $signedk-dominationnumber$ is the maximum value of $\sum _{u\in V}f(u)$ taken over all $minimal$ signed $k$-dominating functions of $G$. In this paper, we study these graph parameters from both algorithmic complexity and graph-theoretic perspectives. We prove that for every fixed $k\ge 1$, the problems of computing these three parameters are all $\mathcal{N}\mathcal{P}$-hard. We also present sharp lower bounds on the signed $k$-domination number and signed total $k$-domination number for general graphs in terms of their minimum and maximum degrees, generalizing several known results about signed domination.

In this paper, we study a pair of simplicial complexes, which we denote by $\mathcal{B}(k,d)$ and $\mathcal{S}\mathcal{T}(k+1,d-k-1)$, for all nonnegative integers $k$ and $d$ with $0\le k\le d-2$. We conjecture that their underlying topological spaces $|\mathcal{B}(k,d)|$ and $|\mathcal{S}\mathcal{T}(k+1,d-k-1)|$ are homeomorphic for all such $k$ and $d$. We answer this question when $k=d-2$ by relating the complexes through a series of well-studied combinatorial operations that transform a combinatorial manifold while preserving its PL-homeomorphism type.

Let $D=(V,A)$ be a finite and simple digraph. A Roman dominating function (RDF) on $D$ is a labeling $f:V(D)\to \{0,1,2\}$ such that every vertex $v$ with label $0$ has a vertex $w$ with label $2$ such that $wv$ is an arc in $D$. The weight of an RDF $f$ is the value $\omega (f)=\sum _{v\in V}f(v)$. The Roman domination number of a digraph $D$, denoted by ${\gamma }_R(D)$, equals the minimum weight of an RDF on $D$. The Roman reinforcement number $r_R(D)$ of a digraph $D$ is the minimum number of arcs that must be added to $D$ in order to decrease the Roman domination number. In this paper, we initiate the study of Roman reinforcement number in digraphs and we present some sharp bounds for $r_R(D)$. In particular, we determine the Roman reinforcement number of some classes of digraphs.

In this paper, some formulae for computing the numbers of spanning trees of the corona and the join of graphs are deduced.

Partially filled $6\times 6$ Sudoku grids are categorized based on the arrangement of the values in the first three rows. This categorization is then employed to determine the number of $6\times 6$ Sudoku grids.

Stankova and West proved in 2002 that the patterns $231$ and $312$ are shape-Wilf-equivalent. Their proof was nonbijective. We give a new characterization of $231$ and $312$ avoiding full rook placements and use this to give a simple bijection that demonstrates the shape-Wilf-equivalence.