The paired domination number ${\gamma }_{pr}\left(G\right)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: ${\gamma }_{pr}\left(\pi G\right)=2{\gamma }_{pr}\left(G\right)$ for all πG; ${\gamma }_{pr}\left(K₂☐G\right)=2{\gamma }_{pr}\left(G\right)$; ${\gamma }_{pr}\left(K₂☐G\right)={\gamma }_{pr}\left(G\right)$.

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of...

A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

Given a graph $G=(V,E)$, if we can partition the vertex set $V$ into two nonempty subsets $V_1$ and $V_2$ which satisfy $\Delta \left(G\left[V_1\right]\right)\le d_1$ and $\Delta \left(G\left[V_2\right]\right)\le d_2$, then we say $G$ has a $({\Delta }_{d_1},{\Delta }_{d_2})$-partition. And we say $G$ admits an $(F_{d_1},F_{d_2})$-partition if $G\left[V_1\right]$ and $G\left[V_2\right]$ are both forests whose maximum degree is at most $d_1$ and $d_2$, respectively. We show that every planar graph with girth at least 5 has an $(F_4,F_4)$-partition.

If D is a dominating set and the induced subgraph G(D) is connected, then D is a connected dominating set. The minimum size of a connected dominating set in G is called connected domination number ${\gamma }_c\left(G\right)$ of G. A graph G is called a perfect connected-dominant graph if $\gamma \left(H\right)={\gamma }_c\left(H\right)$ for each connected induced subgraph H of G.We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P₅ and induced cycle C₅.

A subset $D$ of the vertex set $V\left(G\right)$ of a graph $G$ is called point-set dominating, if for each subset $S\subseteq V\left(G\right)-D$ there exists a vertex $v\in D$ such that the subgraph of $G$ induced by $S\cup \left\{v\right\}$ is connected. The maximum number of classes of a partition of $V\left(G\right)$, all of whose classes are point-set dominating sets, is the point-set domatic number $d_p\left(G\right)$ of $G$. Its basic properties are studied in the paper.

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$, denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $\mathrm{pc}\left(G\right)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$-coloring for a connected bipartite graph $G$ having $\delta \left(G\right)\ge 2$ and a dominating cycle...

A vertex subset S of a graph G is a perfect (resp. quasiperfect) dominating set in G if each vertex v of G∖S is adjacent to only one vertex ($d_v$ ∈ 1,2 vertices) of S. Perfect and quasiperfect dominating sets in the regular tessellation graph of Schläfli symbol 3,6 and in its toroidal quotients are investigated, yielding the classification of their perfect dominating sets and most of their quasiperfect dominating sets S with induced components of the form $K_{\nu }$, where ν ∈ 1,2,3 depends only on S.

Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.

A graph is $2$-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let $F$ be a $2$-stratified graph rooted at some blue vertex $v$. An $F$-coloring of a graph $G$ is a red-blue coloring of the vertices of $G$ in which every blue vertex $v$ belongs to a copy of $F$ rooted at $v$. The $F$-domination number ${\gamma }_F\left(G\right)$ is the minimum number of red vertices in an $F$-coloring of $G$. In this paper, we study $F$-domination where $F$ is...

On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme $${\underline{b}}_n\le g\oplus i\le {\overline{b}}_n$$ où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne $\overline{l}$, l'index λ1, l'indice de Randić R et le nombre de domination β, $\oplus$ désigne l'une des opérations +, -, ×, /, ${\underline{b}}_n$ et ${\overline{b}}_n$ des fonctions de l'ordre n du graphe qui bornent l'expression $g\oplus i$ et sont atteintes pour tout n (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous...

In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective equality...

Dynamic monopolies in graphs have been studied as a model for spreading processes within networks. Together with their dual notion, the generalized degenerate sets, they form the immediate generalization of the classical notions of vertex covers and independent sets in a graph. We present results concerning dynamic monopolies in graphs of given average threshold values extending and generalizing previous results of Khoshkhah et al. [On dynamic monopolies of graphs: The average and strict majority...