Structure and pancyclicity of maximal planar graphs with diameter two

Shu Yu Cui; Yiqiao Wang; Danjun Huang; Hongwei Du; Weifan Wang

doi:10.1007/s10878-021-00749-7

Structure and pancyclicity of maximal planar graphs with diameter two

Shu Yu Cui
, Yiqiao Wang
, Danjun Huang
, Hongwei Du
, Weifan Wang^*

^*Corresponding author for this work

Zhejiang Normal University
Beijing University of Chinese Medicine
Harbin Institute of Technology Shenzhen

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

2 Scopus citations

Abstract

A graph G on n vertices is called non-universal if its maximum degree is at most n- 2. In this paper, we give a structural characterization for non-universal maximal planar graphs with diameter two. In precise, we find 10 basic graphs, and then generate all 25 non-universal maximal planar graphs with diameter two by adding repeatedly and appropriately 3-vertices to some of these 10 basic graphs. As an application, we show that maximal planar graphs with diameter two are pancyclic except five special graphs.

Original language	English
Journal	Journal of Combinatorial Optimization
Volume	43
Issue number	1
DOIs	https://doi.org/10.1007/s10878-021-00749-7
State	Published - Jan 2022
Externally published	Yes

Keywords

Diameter two
Dominating set
Maximal plane graph
Pancyclicity

Access to Document

10.1007/s10878-021-00749-7

Cite this

@article{9481a87495b94917ae4c8691af3a9b44,

title = "Structure and pancyclicity of maximal planar graphs with diameter two",

abstract = "A graph G on n vertices is called non-universal if its maximum degree is at most n- 2. In this paper, we give a structural characterization for non-universal maximal planar graphs with diameter two. In precise, we find 10 basic graphs, and then generate all 25 non-universal maximal planar graphs with diameter two by adding repeatedly and appropriately 3-vertices to some of these 10 basic graphs. As an application, we show that maximal planar graphs with diameter two are pancyclic except five special graphs.",

keywords = "Diameter two, Dominating set, Maximal plane graph, Pancyclicity",

author = "Cui, \{Shu Yu\} and Yiqiao Wang and Danjun Huang and Hongwei Du and Weifan Wang",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2022",

month = jan,

doi = "10.1007/s10878-021-00749-7",

language = "英语",

volume = "43",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Structure and pancyclicity of maximal planar graphs with diameter two

AU - Cui, Shu Yu

AU - Wang, Yiqiao

AU - Huang, Danjun

AU - Du, Hongwei

AU - Wang, Weifan

PY - 2022/1

Y1 - 2022/1

N2 - A graph G on n vertices is called non-universal if its maximum degree is at most n- 2. In this paper, we give a structural characterization for non-universal maximal planar graphs with diameter two. In precise, we find 10 basic graphs, and then generate all 25 non-universal maximal planar graphs with diameter two by adding repeatedly and appropriately 3-vertices to some of these 10 basic graphs. As an application, we show that maximal planar graphs with diameter two are pancyclic except five special graphs.

AB - A graph G on n vertices is called non-universal if its maximum degree is at most n- 2. In this paper, we give a structural characterization for non-universal maximal planar graphs with diameter two. In precise, we find 10 basic graphs, and then generate all 25 non-universal maximal planar graphs with diameter two by adding repeatedly and appropriately 3-vertices to some of these 10 basic graphs. As an application, we show that maximal planar graphs with diameter two are pancyclic except five special graphs.

KW - Diameter two

KW - Dominating set

KW - Maximal plane graph

KW - Pancyclicity

UR - https://www.scopus.com/pages/publications/85105144555

U2 - 10.1007/s10878-021-00749-7

DO - 10.1007/s10878-021-00749-7

M3 - 文章

AN - SCOPUS:85105144555

SN - 1382-6905

VL - 43

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

Structure and pancyclicity of maximal planar graphs with diameter two

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this