F3-domination problem of graphs

Chan Wei Chang; David Kuo; Sheng Chyang Liaw; Jing Ho Yan

doi:10.1007/s10878-012-9563-y

F₃-domination problem of graphs

Chan Wei Chang, David Kuo, Sheng Chyang Liaw, Jing Ho Yan

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Given a graph G and a set S⊆ V(G) a vertex v is said to be ₃ -dominated by a vertex w in S if either v=w, or v∉ S and there exists a vertex u in V(G)-S such that P:wuv is a path in G. A set S⊆ V(G)is an ₃ -dominating set of G if every vertex v is ₃ -dominated by a vertex w in S.The ₃ -domination number of G, denoted by γ F₃(G), is the minimum cardinality of an ₃ -dominating set of G. In this paper, we study the ₃ -domination of Cartesian product of graphs, and give formulas to compute the ₃ -domination number of P_m×P_nand P_m× C_nfor special m,n.

Original language	English
Pages (from-to)	400-413
Number of pages	14
Journal	Journal of Combinatorial Optimization
Volume	28
Issue number	2
DOIs	https://doi.org/10.1007/s10878-012-9563-y
State	Published - Aug 2014

Keywords

Cartesian product
Cycle
Domination
Path

Access to Document

10.1007/s10878-012-9563-y

Cite this

@article{1ab0971f55724e27a42f806a3f953f2c,

title = "F3-domination problem of graphs",

abstract = "Given a graph G and a set S⊆ V(G) a vertex v is said to be 3 -dominated by a vertex w in S if either v=w, or v∉ S and there exists a vertex u in V(G)-S such that P:wuv is a path in G. A set S⊆ V(G)is an 3 -dominating set of G if every vertex v is 3 -dominated by a vertex w in S.The 3 -domination number of G, denoted by γ F3(G), is the minimum cardinality of an 3 -dominating set of G. In this paper, we study the 3 -domination of Cartesian product of graphs, and give formulas to compute the 3 -domination number of Pm×Pnand Pm× Cnfor special m,n.",

keywords = "Cartesian product, Cycle, Domination, Path",

author = "Chang, {Chan Wei} and David Kuo and Liaw, {Sheng Chyang} and Yan, {Jing Ho}",

note = "Funding Information: Acknowledgments David Kuo was supported in part by the National Science Council undergrants NSC99-2115-M-156-003-MY2. Jing-Ho Yan was supported in part by the National Science Council under grants NSC97-2115-M-259-002-MY3.",

year = "2014",

month = aug,

doi = "10.1007/s10878-012-9563-y",

language = "???core.languages.en_GB???",

volume = "28",

pages = "400--413",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

number = "2",

}

TY - JOUR

T1 - F3-domination problem of graphs

AU - Chang, Chan Wei

AU - Kuo, David

AU - Liaw, Sheng Chyang

AU - Yan, Jing Ho

N1 - Funding Information: Acknowledgments David Kuo was supported in part by the National Science Council undergrants NSC99-2115-M-156-003-MY2. Jing-Ho Yan was supported in part by the National Science Council under grants NSC97-2115-M-259-002-MY3.

PY - 2014/8

Y1 - 2014/8

N2 - Given a graph G and a set S⊆ V(G) a vertex v is said to be 3 -dominated by a vertex w in S if either v=w, or v∉ S and there exists a vertex u in V(G)-S such that P:wuv is a path in G. A set S⊆ V(G)is an 3 -dominating set of G if every vertex v is 3 -dominated by a vertex w in S.The 3 -domination number of G, denoted by γ F3(G), is the minimum cardinality of an 3 -dominating set of G. In this paper, we study the 3 -domination of Cartesian product of graphs, and give formulas to compute the 3 -domination number of Pm×Pnand Pm× Cnfor special m,n.

AB - Given a graph G and a set S⊆ V(G) a vertex v is said to be 3 -dominated by a vertex w in S if either v=w, or v∉ S and there exists a vertex u in V(G)-S such that P:wuv is a path in G. A set S⊆ V(G)is an 3 -dominating set of G if every vertex v is 3 -dominated by a vertex w in S.The 3 -domination number of G, denoted by γ F3(G), is the minimum cardinality of an 3 -dominating set of G. In this paper, we study the 3 -domination of Cartesian product of graphs, and give formulas to compute the 3 -domination number of Pm×Pnand Pm× Cnfor special m,n.

KW - Cartesian product

KW - Cycle

KW - Domination

KW - Path

UR - http://www.scopus.com/inward/record.url?scp=84903554642&partnerID=8YFLogxK

U2 - 10.1007/s10878-012-9563-y

DO - 10.1007/s10878-012-9563-y

M3 - 期刊論文

AN - SCOPUS:84903554642

SN - 1382-6905

VL - 28

SP - 400

EP - 413

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 2

ER -