Changing of the domination number of a graph: edge multisubdivision and edge removal

Title:

Changing of the domination number of a graph: edge multisubdivision and edge removal

Creator:

Samodivkin, Vladimir

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:d65c0f63-c154-4eba-83c2-21d2a448e105
uuid:d65c0f63-c154-4eba-83c2-21d2a448e105
doi:10.21136/MB.2017.0009-15

Subject:

dominating set, edge subdivision, domination multisubdivision number, and hereditary graph property

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

For a graphical property P and a graph G, a subset S of vertices of G is a P-set if the subgraph induced by S has the property P. The domination number with respect to the property P, denoted by γP (G), is the minimum cardinality of a dominating P-set. We define the domination multisubdivision number with respect to P, denoted by msdP (G), as a minimum positive integer k such that there exists an edge which must be subdivided k times to change γP (G). In this paper (a) we present necessary and sufficient conditions for a change of γP (G) after subdividing an edge of G once, (b) we prove that if e is an edge of a graph G then γP (Ge,1) < γP (G) if and only if γP (G − e) < γP (G) (Ge,t denotes the graph obtained from G by subdivision of e with t vertices), (c) we also prove that for every edge of a graph G we have γP (G − e) 6 γP (Ge,3) ≤ γP (G − e) + 1, and (d) we show that msdP (G) 6 3, where P is hereditary and closed under union with K1.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

9-20

Source:

Mathematica bohemica | 2017 Volume:142 | Number:1

Harvested from:

CDK

Metadata only:

false