Connected partition dimensions of graphs

Varaporn Saenpholphat; Ping Zhang

Displaying similar documents to “Connected partition dimensions of graphs”

Perfect connected-dominant graphs

Igor Edmundovich Zverovich (2003)

Discussiones Mathematicae Graph Theory

Similarity:

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 $γ_{c} (G)$ of G. A graph G is called a perfect connected-dominant graph if $γ (H) = γ_{c} (H)$ 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₅.

Connected domatic number in planar graphs

Bert L. Hartnell, Douglas F. Rall (2001)

Czechoslovak Mathematical Journal

Similarity:

A dominating set in a graph $G$ is a connected dominating set of $G$ if it induces a connected subgraph of $G$ . The connected domatic number of $G$ is the maximum number of pairwise disjoint, connected dominating sets in $V (G)$ . We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic...

Connected global offensive k-alliances in graphs

Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

We consider finite graphs G with vertex set V(G). For a subset S ⊆ V(G), we define by G[S] the subgraph induced by S. By n(G) = |V(G) | and δ(G) we denote the order and the minimum degree of G, respectively. Let k be a positive integer. A subset S ⊆ V(G) is a connected global offensive k-alliance of the connected graph G, if G[S] is connected and |N(v) ∩ S | ≥ |N(v) -S | + k for every vertex v ∈ V(G) -S, where N(v) is the neighborhood of v. The connected global offensive k-alliance number...

Connected resolvability of graphs

Varaporn Saenpholphat, Ping Zhang (2003)

Czechoslovak Mathematical Journal

Similarity:

For an ordered set $W = {w_{1}, w_{2}, \dots, w_{k}}$ of vertices and a vertex $v$ in a connected graph $G$ , the representation of $v$ with respect to $W$ is the $k$ -vector $r (v | W)$ = ( $d (v, w_{1})$ , $d (v, w_{2}), \dots, d (v, w_{k}))$ , where $d (x, y)$ represents the distance between the vertices $x$ and $y$ . The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$ . A resolving set for $G$ containing a minimum number of vertices is a basis for $G$ . The dimension $dim (G)$ is the number of vertices in a basis for $G$ . A resolving set $W$ of $G$ is connected...

The order of uniquely partitionable graphs

Izak Broere, Marietjie Frick, Peter Mihók (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition V₁,...,Vₙ of V(G) such that, for each i = 1,...,n, the subgraph of G induced by $V_{i}$ has property $_{i}$ . If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.

On odd and semi-odd linear partitions of cubic graphs

Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe, Adam P. Wojda (2009)

Discussiones Mathematicae Graph Theory

Similarity:

A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G) = 2. A linear partition $L = (L_{B}, L_{R})$ is said to be odd whenever each path of $L_{B} \cup L_{R}$ has odd length and semi-odd whenever each path of $L_{B}$ (or each path of $L_{R}$ ) has odd length. In...

Total outer-connected domination in trees

Joanna Cyman (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. Set D ⊆ V(G) is a total outer-connected dominating set of G if D is a total dominating set in G and G[V(G)-D] is connected. The total outer-connected domination number of G, denoted by $γ_{t c} (G)$ , is the smallest cardinality of a total outer-connected dominating set of G. We show that if T is a tree of order n, then $γ_{t c} (T) \geq ⎡ 2 n / 3 ⎤$ . Moreover, we constructively characterize the family of extremal trees T of order n achieving this lower bound.

Uniquely partitionable graphs

Jozef Bucko, Marietjie Frick, Peter Mihók, Roman Vasky (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G [V_{i}]$ induced by $V_{i}$ has property $_{i}$ ; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property...

The contractible subgraph of $5$ -connected graphs

Chengfu Qin, Xiaofeng Guo, Weihua Yang (2013)

Czechoslovak Mathematical Journal

Similarity:

An edge $e$ of a $k$ -connected graph $G$ is said to be $k$ -removable if $G - e$ is still $k$ -connected. A subgraph $H$ of a $k$ -connected graph is said to be $k$ -contractible if its contraction results still in a $k$ -connected graph. A $k$ -connected graph with neither removable edge nor contractible subgraph is said to be minor minimally $k$ -connected. In this paper, we show that there is a contractible subgraph in a $5$ -connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex...

Graph domination in distance two

Gábor Bacsó, Attila Tálos, Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $D o m D o m_{u} = D o m ₂_{u}$ holds for $_{u}$ = all connected graphs without induced $P_{u}$ (u ≥ 2). (In particular,...

On connected resolving decompositions in graphs

Varaporn Saenpholphat, Ping Zhang (2004)

Czechoslovak Mathematical Journal

Similarity:

For an ordered $k$ -decomposition $𝒟 = {G_{1}, G_{2}, \dots, G_{k}}$ of a connected graph $G$ and an edge $e$ of $G$ , the $𝒟$ -code of $e$ is the $k$ -tuple $c_{𝒟} (e) = (d (e, G_{1}), d (e, G_{2}), ..., d (e, G_{k}))$ , where $d (e, G_{i})$ is the distance from $e$ to $G_{i}$ . A decomposition $𝒟$ is resolving if every two distinct edges of $G$ have distinct $𝒟$ -codes. The minimum $k$ for which $G$ has a resolving $k$ -decomposition is its decomposition dimension ${dim}_{d} (G)$ . A resolving decomposition $𝒟$ of $G$ is connected if each $G_{i}$ is connected for $1 \leq i \leq k$ . The minimum $k$ for which $G$ has a connected resolving $k$ -decomposition is its connected decomposition...