Dominating cliques in graphs

Margaret B. Cozzens; Laura L. Kelleher

doi:10.1016/0012-365X(90)90353-J

Dominating cliques in graphs

Margaret B. Cozzens, Laura L. Kelleher

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

54 Scopus citations

Abstract

A set of vertices is a dominating set in a graph if every vertex not in the dominating set is adjacent to one or more vertices in the dominating set. A dominating clique is a dominating set that induces a complete subgraph. Forbidden subgraph conditions sufficient to imply the existence of a dominating clique are given. For certain classes of graphs, a polynomial algorithm is given for finding a dominating clique. A forbidden subgraph characterization is given for a class of graphs that have a connected dominating set of size three.

Original language	English (US)
Pages (from-to)	101-116
Number of pages	16
Journal	Discrete Mathematics
Volume	86
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(90)90353-J
State	Published - Dec 14 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(90)90353-J

Cite this

@article{692ec90e701640a092029940d87f1f20,

title = "Dominating cliques in graphs",

abstract = "A set of vertices is a dominating set in a graph if every vertex not in the dominating set is adjacent to one or more vertices in the dominating set. A dominating clique is a dominating set that induces a complete subgraph. Forbidden subgraph conditions sufficient to imply the existence of a dominating clique are given. For certain classes of graphs, a polynomial algorithm is given for finding a dominating clique. A forbidden subgraph characterization is given for a class of graphs that have a connected dominating set of size three.",

author = "Cozzens, {Margaret B.} and Kelleher, {Laura L.}",

year = "1990",

month = dec,

day = "14",

doi = "10.1016/0012-365X(90)90353-J",

language = "English (US)",

volume = "86",

pages = "101--116",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Dominating cliques in graphs

AU - Cozzens, Margaret B.

AU - Kelleher, Laura L.

PY - 1990/12/14

Y1 - 1990/12/14

N2 - A set of vertices is a dominating set in a graph if every vertex not in the dominating set is adjacent to one or more vertices in the dominating set. A dominating clique is a dominating set that induces a complete subgraph. Forbidden subgraph conditions sufficient to imply the existence of a dominating clique are given. For certain classes of graphs, a polynomial algorithm is given for finding a dominating clique. A forbidden subgraph characterization is given for a class of graphs that have a connected dominating set of size three.

AB - A set of vertices is a dominating set in a graph if every vertex not in the dominating set is adjacent to one or more vertices in the dominating set. A dominating clique is a dominating set that induces a complete subgraph. Forbidden subgraph conditions sufficient to imply the existence of a dominating clique are given. For certain classes of graphs, a polynomial algorithm is given for finding a dominating clique. A forbidden subgraph characterization is given for a class of graphs that have a connected dominating set of size three.

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

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

U2 - 10.1016/0012-365X(90)90353-J

DO - 10.1016/0012-365X(90)90353-J

M3 - Article

AN - SCOPUS:38249017737

SN - 0012-365X

VL - 86

SP - 101

EP - 116

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Dominating cliques in graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this