We use a dynamic programming algorithm to establish a lower bound on the domination number of complete grid graphs $G_{m,n}$. The bound is within $5$ of a known upper bound that has been conjectured to be the exact domination number of the complete grid graphs.

A large set of KTS($v$), denoted by LKTS($v$), is a collection of ($v-2$) pairwise disjoint KTS($v$) on the same set. In this paper, it is proved that there exists an LKTS($3^n\cdot 91$) for any integer $n\ge 1$.

If $x$ is a vertex of a digraph $D$, then we denote by $d^{+}(x)$ and $d^{-}(x)$ the outdegree and the indegree of $x$, respectively. The global irregularity of a digraph $D$ is defined by $i_g(D)=max\{d^{+}(x),d^{-}(x)\}–min\{d^{+}(y),d^{-}(y)\}$ over all vertices $x$ and $y$ of $D$ (including $x=y$). If $i_g(D)=0$, then $D$ is regular, and if $i_g(D)\le 1$, then $D$ is called almost regular. The local irregularity is defined as $i_l(D)=max[|d^{+}(x)–d^{-}(x)|]$ over all vertices $x$ of $D$. The path covering number of $D$ is the minimum number of directed paths in $D$ that are pairwise vertex disjoint and cover the vertices of $D$. A semicomplete $c$-partite digraph is a digraph obtained from a complete $c$-partite graph by replacing each edge with an arc, or a pair of mutually opposite arcs with the same end vertices. If a semicomplete $c$-partite digraph $D$ does not contain an oriented cycle of length two, then $D$ is called a $c$-partite tournament.
In 2000, Gutin and Yeo [7] proved sufficient conditions for the local irregularity of a semicomplete multipartite digraph to secure a path covering number of at most $k$. In this paper, we will give a useful supplement to this result by using bounds for the global irregularity that guarantee a path covering number of at most $k$. As an application, we will present sufficient conditions for close to regular multipartite tournaments containing a Hamiltonian path. Especially, we will characterize almost regular $c$-partite tournaments containing a Hamiltonian path.

An extended $7$-cycle system of order $n$ is an ordered pair $(V,B)$, where $B$ is a collection of edge-disjoint 7-cycles, 3-tadpoles, and loops which partition the edges of the graph $K_n^{+}$ whose vertex set is an $n$-set $V$. In this paper, we show that an extended 7-cycle system of order $n$ exists for all $n$ except $n=2,3,$ and $5$.

A grid graph is a finite induced subgraph of the infinite 2-dimensional grid defined by $\mathbb{Z}\times \mathbb{Z}$ and all edges between pairs of vertices from $\mathbb{Z}\times \mathbb{Z}$ at Euclidean distance precisely $1$. An $m\times n$-rectangular grid graph is induced by all vertices with coordinates from $1$ to $m$ and from $1$ to $n$, respectively. A natural drawing of a (rectangular) grid graph $G$ is obtained by drawing its vertices in ${\mathbb{R}}^2$ according to their coordinates. We consider a subclass of the rectangular grid graphs obtained by deleting some vertices from the corners. Apart from the outer face, all (inner) faces of these graphs have area one (bounded by a $4$-cycle) in a natural drawing of these graphs. We determine which of these graphs contain a Hamilton cycle, i.e., a cycle containing all vertices, and solve the problem of determining a spanning $2$-connected subgraph with as few edges as possible for all these graphs.

The (previously studied) notions of secure domination and of weak Roman domination involve the construction of protection strategies in a simple graph $G=(V,E)$, by utilizing the minimum number of guards needed at vertices in $V$ to protect $G$ in different scenarios (these minimum numbers are called the secure [weak Roman] domination parameters for the graph). In this paper, these notions are generalized in the sense that safe configurations in $G$ are not merely sought after one move, but rather after each of $k\ge 1$ moves. Some general properties of these generalized domination parameters are established, after which the parameter values are found for certain simple graph structures (such as paths, cycles, multipartite graphs, and products of complete graphs, cycles, and paths).

We establish necessary and sufficient conditions on $m$ and $n$ for $K_m\times K_n$, the Cartesian product of two complete graphs, to be decomposable into cycles of length $8$. We also provide a complete classification of the leaves that are possible with maximum packings of complete graphs with $8$-cycles.

We consider the rank of the adjacency matrix of the line graph for some classes of regular graphs. In particular, we study the line graphs of cycles, paths, complete graphs, complete bipartite and multipartite graphs, circulant graphs of degrees three and four, and some Cartesian graph products.

For each vertex $v$ in a graph $G$, let there be associated a particular type of a subgraph $F_v$ of $G$. In this context, the vertex $v$ is said to dominate $F_v$. A set $S$ of vertices of $G$ is called a full dominating set if every vertex of $G$ belongs to a subgraph $F_v$ of $G$ for some $v\in S$ and every edge of $G$ belongs to a subgraph $F_w$ of $G$ for some $w\in S$. The minimum cardinality of a full dominating set of $G$ is its full domination number ${\gamma }_F(G)$. A full dominating set of $G$ of cardinality ${\gamma }_F(G)$ is called a ${\gamma }_F$-set of $G$.

We study three types of full domination in graphs: full star domination, where $F_v$ is the maximum star centered at $v$; full closed domination, where $F_v$ is the subgraph induced by the closed neighborhood of $v$; and full open domination, where $F_v$ is the subgraph induced by the open neighborhood of $v$.

A subset $T$ of a ${\gamma }_F$-set $S$ in a graph $G$ is a forcing subset for $S$ if $S$ is the unique ${\gamma }_F$-set containing $T$. The forcing full domination number of $S$ in $G$ is the minimum cardinality of a forcing subset for $S$, and the forcing full domination number $f_{{\gamma }_F}(G)$ of the graph $G$ is the minimum forcing full domination number among all ${\gamma }_F$-sets of $G$.

We present several realization results concerning forcing parameters in full domination.

A minimum feedback arc set of a digraph is a smallest sized set of arcs whose reversal makes the resulting digraph acyclic. Given an acyclic digraph $D$, we seek a smallest sized tournament $T$ having $A(D)$ as a minimum feedback arc set. The reversing number of a digraph $D$ equals $|V(T)|–|V(D)|$. We investigate the reversing number of the $k$th power of directed Hamiltonian path $P_n^k$, when $k$ is fixed and $n$ tends to infinity. We show that even for small values of $k$, where $|A(P_n^k)|$ is much closer to $|A(P_n)|$ than $|A(T_n)|$, the opposite relationship holds for the reversing number.

A union closed (UC) family $\mathcal{A}$ is a finite family of sets such that the union of any two sets in $\mathcal{A}$ is also in $\mathcal{A}$. Peter Frankl conjectured in 1979 that for every union closed family $\mathcal{A}$, there exists some $x$ contained in at least half the members of $\mathcal{A}$. In this paper, we show that if a UC family $\mathcal{A}$ fails the conjecture, then no element can appear in more than two of its $3$-sets, and so the number of $3$-sets in $\mathcal{A}$ can be no more than $\frac{2n}{3}$.

A $(k,d)$-total coloring ($k,d\in \mathbb{N},k\ge 2d$) of a graph $G$ is an assignment $c$ of colors $\{0,1,\dots ,k-1\}$ to the vertices and edges of $G$ such that $d\le |c(x_i)–c(x_j)|\le k–d$ whenever $x_i$ and $x_j$ are two adjacent edges, two adjacent vertices, or an edge incident to a vertex. The circular total chromatic number ${\chi }_c”(G)$ is defined by ${\chi }_c”(G)=inf\{k/d:G\text{ has a }(k,d)\text{-total coloring}\}.$ It was proved that $\chi ”(G)–1<{\chi }_c^{″}(G)\le {\chi }^{″}(G)$ — where ${\chi }^{″}(G)$ is the total chromatic number of $G$ — with equality for all type-1 graphs and most of the so far considered type-2 graphs. We determine an infinite class of graphs $G$ such that ${\chi }_c^{″}(G)<{\chi }^{″}(G)$ and we list all graphs of order $<7$ with this property.

In this paper we consider a variation of the classical Turán-type extremal problems. Let $S$ be an $n$-term graphical sequence, and $\sigma (S)$ be the sum of the terms in $S$. Let $H$ be a graph. The problem is to determine the smallest even $l$ such that any $n$-term graphical sequence $S$ having $\sigma (S)\ge l$ has a realization containing $H$ as a subgraph. Denote this value $l$ by $\sigma (H,n)$. We show $\sigma (C_{2m+1},n)=m(2n–m–1)+2,\text{for }m\ge 3,n\ge 3m;$ $\sigma (C_{2m+2},n)=m(2n–m–1)+4,\text{for }m\ge 3,n\ge 5m–2.$

We first prove that if $G$ is a connected graph with $n$ vertices and chromatic number $\chi (G)=k\ge 2$, then its independent domination number

$$i(G)\le \lceil \frac{(k-1)}{k}n\rceil –(k-2).$$

This bound is tight and remains so for planar graphs. We then prove that the independent domination number of a diameter two planar graph on $n$ vertices is at most $\lceil \frac{n}{3}\rceil$.

Hill, Landjev, Jones, Storme, and Barat proved in a previous article on caps in $PG(5,3)$ and $PG(6,3)$ that every 53-cap in $PG(5,3)$ is contained in the 56-cap of Hill and that there exist complete 48-caps in $PG(5,3)$. The first result was used to lower the upper bound on $m_2(6,3)$ on the size of caps in $PG(6,3)$ from 164 to 154. Presently, the known upper bound on $m_2(6,3)$ is 148. In this article, using computer searches, we prove that every 49-cap in $PG(5,3)$ is contained in a 56-cap, and that every 48-cap, having a 20-hyperplane with at most 8-solids, is also contained in a 56-cap. Computer searches for caps in $PG(6,3)$ which use the computer results of $PG(5,3)$ then lower the upper bound on $m_2(6,3)$ to $m_2(6,3)\le 136$. So now we know that $112\le m_2(6,3)\le 136$.

Let $\delta (G)$ and $\lambda (G)$ be the minimum degree and edge-connectivity of a graph $G$, respectively. A graph $G$ is maximally edge-connected if $\lambda (G)=\delta (G)$ and super-edge-connected if every minimum edge cut consists of edges adjacent to a vertex of minimum degree.

In this paper, sufficient conditions for super-edge-connected graphs depending on the clique number and the minimum degree are presented. These results show that some known sufficient conditions for maximally edge-connected graphs even lead to super-edge-connected graphs.