Let $G$ be a graph with vertex set $V\left(G\right)$, and let $k\ge 1$ be an integer. A subset $D\subseteq V\left(G\right)$ is called a $k$-dominating set if every vertex $v\in V\left(G\right)-D$ has at least $k$ neighbors in $D$. The $k$-domination number ${\gamma }_k\left(G\right)$ of $G$ is the minimum cardinality of a $k$-dominating set in $G$. If $G$ is a graph with minimum degree $\delta \left(G\right)\ge k+1$, then we prove that $${\gamma }_{k+1}\left(G\right)\le \frac{\left|V\left(G\right)\right|+{\gamma }_k\left(G\right)}{2}.$$ In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

Given graphs A, B and C for which A×C ≅ B×C, it is not generally true that A ≅ B. However, it is known that A×C ≅ B×C implies A ≅ B provided that C is non-bipartite, or that there are homomorphisms from A and B to C. This note proves an additional cancellation property. We show that if B and C are bipartite, then A×C ≅ B×C implies A ≅ B if and only if no component of B admits an involution that interchanges its partite sets.

T. Brown proved that whenever we color ${𝒫}_f\left(\mathbb{N}\right)$ (the set of finite subsets of natural numbers) with finitely many colors, we find a monochromatic structure, called an arithmetic copy of an $\omega$-forest. In this paper we show a canonical extension of this theorem; i.eẇhenever we color ${𝒫}_f\left(\mathbb{N}\right)$ with arbitrarily many colors, we find a canonically colored arithmetic copy of an $\omega$-forest. The five types of the canonical coloring are determined. This solves a problem of T. Brown.

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model${\text{IPM}}_k$(n), a generalization of the sand pile model$\text{SPM}$(n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice ${\text{IPM}}_k$(n): this lets us design an algorithm which generates all the ice piles of ${\text{IPM}}_k$(n) in amortized time O(1) and in space O($\sqrt{n}$).

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model${\text{IPM}}_k$(n), a generalization of the sand pile model$\text{SPM}$(n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice ${\text{IPM}}_k$(n): this lets us design an algorithm which generates all the ice piles of ${\text{IPM}}_k$(n) in amortized time O(1) and in space O($\sqrt{n}$).

A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150...

The order of every finite group $G$ can be expressed as a product of coprime positive integers $m_1,\cdots ,m_t$ such that $\pi \left(m_i\right)$ is a connected component of the prime graph of $G$. The integers $m_1,\cdots ,m_t$ are called the order components of $G$. Some non-abelian simple groups are known to be uniquely determined by their order components. As the main result of this paper, we show that the projective symplectic groups $C_2\left(q\right)$ where $q>5$ are also uniquely determined by their order components. As corollaries of this result, the validities of a...