A note on domination 3-edge-critical planar graphs

•A graph G is 3-edge-critical if γ(G)=3 and γ(G+xy)≤2 for all x,y∈V(G) where γ(G) is the domination number of G.•Ananchuen and Plummer proved that every 3-connected 3-edge-critical planar graph having even order is bicritical.•We show that the class of 3-edge-critical planar graphs is very small by...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2019-02, Vol.142, p.64-67
Main Authors: Furuya, Michitaka, Matsumoto, Naoki
Format: Article
Language:English
Subjects:
Bicritical graph
Combinatorial problems
Domination 3-edge-critical graph
Planar graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•A graph G is 3-edge-critical if γ(G)=3 and γ(G+xy)≤2 for all x,y∈V(G) where γ(G) is the domination number of G.•Ananchuen and Plummer proved that every 3-connected 3-edge-critical planar graph having even order is bicritical.•We show that the class of 3-edge-critical planar graphs is very small by proving that the order of 3-edge-critical graphs is at most 23.•Consequently, any results concerning 3-edge-critical planar graphs can be easily proved. For a graph G, we let γ(G) denote the domination number of G. A graph G is 3-edge-critical if γ(G)=3 and γ(G+xy)≤2 for all x,y∈V(G) with xy∉E(G). In this note, we show that the order of a connected 3-edge-critical planar graph is at most 23.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2018.10.014