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] The decycling number of generalized Petersen graphs
    Gao, Liqing
    Xu, Xirong
    Wang, Jian
    Zhu, Dejun
    Yang, Yuansheng
    DISCRETE APPLIED MATHEMATICS, 2015, 181 : 297 - 300
  • [2] On the diameter of generalized Petersen graphs
    Loudiki, Laila
    Kchikech, Mustapha
    INTERNATIONAL JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE, 2024, 19 (04) : 1035 - 1042
  • [3] Generalizing the generalized Petersen graphs
    Sarazin, Marko Lovrecic
    Pacco, Walter
    Previtali, Andrea
    DISCRETE MATHEMATICS, 2007, 307 (3-5) : 534 - 543
  • [4] On the domination number of the generalized Petersen graphs
    Behzad, Arash
    Behzad, Mehdi
    Praeger, Cheryl E.
    DISCRETE MATHEMATICS, 2008, 308 (04) : 603 - 610
  • [5] Component connectivity of generalized Petersen graphs
    Ferrero, Daniela
    Hanusch, Sarah
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2014, 91 (09) : 1940 - 1963
  • [6] CIRCULAR WIRELENGTH OF GENERALIZED PETERSEN GRAPHS
    Rajasingh, Indra
    Arockiaraj, M.
    Rajan, Bharati
    Manuel, Paul
    JOURNAL OF INTERCONNECTION NETWORKS, 2011, 12 (04) : 319 - 335
  • [7] Independence number of generalized Petersen graphs
    Besharati, Nazli
    Ebrahimi, J. B.
    Azadi, A.
    ARS COMBINATORIA, 2016, 124 : 239 - 255
  • [8] The isomorphism classes of the generalized Petersen graphs
    Steimle, Alice
    Staton, William
    DISCRETE MATHEMATICS, 2009, 309 (01) : 231 - 237
  • [9] On the cooling number of the generalized Petersen graphs
    Sim, Kai An
    Wong, Kok Bin
    AIMS MATHEMATICS, 2024, 9 (12): : 36351 - 36370
  • [10] On the Burning Number of Generalized Petersen Graphs
    Sim, Kai An
    Tan, Ta Sheng
    Wong, Kok Bin
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2018, 41 (03) : 1657 - 1670
12345