A subset $D$ of the vertex set $V\left(G\right)$ of a graph $G$ is called dominating in $G$, if each vertex of $G$ either is in $D$, or is adjacent to a vertex of $D$. If moreover the subgraph $<D>$ of $G$ induced by $D$ is regular of degree 1, then $D$ is called an induced-paired dominating set in $G$. A partition of $V\left(G\right)$, each of whose classes is an induced-paired dominating set in $G$, is called an induced-paired domatic partition of $G$. The maximum number of classes of an induced-paired domatic partition of $G$ is the induced-paired domatic...

Let $a=(a_1,a_2,...,a_n)$ be a nonincreasing sequence of positive real numbers. Denote by $S=\{1,2,...,n\}$ the index set and by $J_k=\{I=\{r_1,r_2,...,r_k\}$, $1\le r_1<r_2<\cdots <r_k\le n\}$ the set of all subsets of $S$ of cardinality $k$, $1\le k\le n-1$. In addition, denote by $a_I=a_{r_1}+a_{r_2}+\cdots +a_{r_k}$, $1\le k\le n-1$, $1\le r_1<r_2<\cdots <r_k\le n$, the sum of $k$ arbitrary elements of sequence $a$, where $a_{I_1}=a_1+a_2+\cdots +a_k$ and $a_{I_n}=a_{n-k+1}+a_{n-k+2}+\cdots +a_n$. We consider bounds of the quantities $R{S}_k\left(a\right)=a_{I_1}/a_{I_n}$, $L{S}_k\left(a\right)=a_{I_1}-a_{I_n}$ and $S_{k,\alpha }\left(a\right)={\sum }_{I\in J_k}{a}_I^{\alpha }$ in terms of $A={\sum }_{i=1}^n{a}_i$ and $B={\sum }_{i=1}^n{a}_i^2$. Then we use the obtained results to generalize some results regarding Laplacian and normalized Laplacian eigenvalues of graphs.

Let $f$ be an integer-valued function defined on the vertex set $V\left(G\right)$ of a graph $G$. A subset $D$ of $V\left(G\right)$ is an $f$-dominating set if each vertex $x$ outside $D$ is adjacent to at least $f\left(x\right)$ vertices in $D$. The minimum number of vertices in an $f$-dominating set is defined to be the $f$-domination number, denoted by ${\gamma }_f\left(G\right)$. In a similar way one can define the connected and total $f$-domination numbers ${\gamma }_{c,f}\left(G\right)$ and ${\gamma }_{t,f}\left(G\right)$. If $f\left(x\right)=1$ for all vertices $x$, then these are the ordinary domination number, connected domination number and total domination...

In this paper, we construct infinite families of tight regular tournaments. In particular, we prove that two classes of regular tournaments, tame molds and ample tournaments are tight. We exhibit an infinite family of 3-dichromatic tight tournaments. With this family we positively answer to one case of a conjecture posed by V. Neumann-Lara. Finally, we show that any tournament with a tight mold is also tight.

We study the thresholds for the emergence of various properties in random subgraphs of (ℕ, <). In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.

The paper concerns infinite paths (in particular, the maximum number of pairwise vertex-disjoint ones) in locally finite graphs and in spanning trees of such graphs.