Recognizing generalized Petersen graphs in linear time

被引：2
|
作者：
Krnc, Matjaz [1 ,2 ]
Wilson, Robin J. [3 ,4 ]
机构：
[1] Univ Salzburg, Dept Comp Sci, Salzburg, Austria
[2] Univ Primorska, FAMNIT, Koper, Slovenia
[3] Open Univ, Milton Keynes, Bucks, England
[4] London Sch Econ, London, England
来源：
DISCRETE APPLIED MATHEMATICS | 2020年 / 283卷
关键词：
Graph recognition; Generalized Petersen graphs; Linear algorithms; CYCLES;
D O I：
10.1016/j.dam.2020.03.007
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
By identifying a local property which structurally classifies any edge, we show that the family of generalized Petersen graphs can be recognized in linear time. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页码：756 / 761
页数：6
相关论文
共 50 条
  • [1] Canonical double covers of generalized Petersen graphs, and double generalized Petersen graphs
    Qin, Yan-Li
    Xia, Binzhou
    Zhou, Sanming
    JOURNAL OF GRAPH THEORY, 2021, 97 (01) : 70 - 81
  • [2] RECOGNIZING OUTERPLANAR GRAPHS IN LINEAR TIME
    WIEGERS, M
    LECTURE NOTES IN COMPUTER SCIENCE, 1987, 246 : 165 - 176
  • [3] Domination in generalized Petersen graphs
    Bohdan Zelinka
    Czechoslovak Mathematical Journal, 2002, 52 : 11 - 16
  • [4] GROUPS OF GENERALIZED PETERSEN GRAPHS
    FRUCHT, R
    GRAVER, JE
    WATKINS, ME
    PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY-MATHEMATICAL AND PHYSICAL SCIENCES, 1971, 70 (SEP): : 211 - &
  • [5] On the diameter of generalized Petersen graphs
    Loudiki, Laila
    Kchikech, Mustapha
    INTERNATIONAL JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE, 2024, 19 (04): : 1035 - 1042
  • [6] OPTIMAL GENERALIZED PETERSEN GRAPHS
    BEENKER, GFM
    VANLINT, JH
    PHILIPS JOURNAL OF RESEARCH, 1988, 43 (02) : 129 - 136
  • [7] The spectrum of generalized Petersen graphs
    Gera, Ralucca
    Stanica, Pantelimon
    AUSTRALASIAN JOURNAL OF COMBINATORICS, 2011, 49 : 39 - 45
  • [8] A linear-time certifying algorithm for recognizing generalized series-parallel graphs
    Chin, Francis Y. L.
    Ting, Hing-Fung
    Tsin, Yung H.
    Zhang, Yong
    DISCRETE APPLIED MATHEMATICS, 2023, 325 : 152 - 171
  • [9] On the reliability of generalized Petersen graphs
    Ekinci, Gulnaz Boruzanli
    Gauci, John Baptist
    DISCRETE APPLIED MATHEMATICS, 2019, 252 : 2 - 9
  • [10] Domination in generalized Petersen graphs
    Zelinka, B
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2002, 52 (01) : 11 - 16
12345