On orienting graphs for connectivity: Projective planes and Halin graphs

被引：0
作者：
Cheriyan, Joseph [1 ]
Zou, Chenglong [2 ]
机构：
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
[2] Univ British Columbia, Dept Math, Vancouver, BC, Canada
来源：
OPERATIONS RESEARCH LETTERS | 2012年 / 40卷 / 05期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Graph connectivity; Graph orientations; Element connectivity; Hypergraphs; Projective planes; Halin graphs; ORIENTATIONS;
D O I：
10.1016/j.orl.2012.06.004
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
Nash-Williams proved that the edges of a k-edge connected (undirected) graph can be oriented such that the resulting directed graph is left perpendiculark/2right perpendicular-edge connected. A long-standing goal in the area is to obtain analogous results for other types of connectivity, such as node connectivity, element connectivity, and hypergraph edge connectivity. We focus on two special classes of graphs, namely, incidence graphs of projective planes and (generalized) Halin graphs, and we prove some analogs of Nash-Williams' result for these classes. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：337 / 341
页数：5
相关论文
共 50 条
  • [21] A FAST ALGORITHM FOR MINING GRAPHS OF PRESCRIBED CONNECTIVITY
    Vanetik, Natalia
    KDIR 2011: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND INFORMATION RETRIEVAL, 2011, : 5 - 13
  • [22] On strong Menger-connectivity of star graphs
    Oh, E
    Chen, FE
    DISCRETE APPLIED MATHEMATICS, 2003, 129 (2-3) : 499 - 511
  • [23] Fast Distributed Algorithms for Connectivity and MST in Large Graphs
    Pandurangan, Gopal
    Robinson, Peter
    Scquizzato, Michele
    ACM TRANSACTIONS ON PARALLEL COMPUTING, 2018, 5 (01)
  • [24] Zero-One Laws for Connectivity in Random Key Graphs
    Yagan, Osman
    Makowski, Armand M.
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2012, 58 (05) : 2983 - 2999
  • [25] Characterization of 3-Regular Halin Graphs with Edge-face Total Chromatic Number Equal to Four
    Chan, W. H.
    Lam, Peter C. B.
    Shiu, W. C.
    ARS COMBINATORIA, 2014, 113 : 257 - 262
  • [26] Orthomorphisms and the construction of projective planes
    Lazebnik, F
    Thomason, A
    MATHEMATICS OF COMPUTATION, 2004, 73 (247) : 1547 - 1557
  • [27] INVARIANT UNIVERSALITY FOR PROJECTIVE PLANES
    Paolini, Gianluca
    REPORTS ON MATHEMATICAL LOGIC, 2023, 58 : 15 - 27
  • [28] On 2-Strong Connectivity Orientations of Mixed Graphs and Related Problems
    Georgiadis, Loukas
    Kefallinos, Dionysios
    Kosinas, Evangelos
    COMBINATORIAL ALGORITHMS, IWOCA 2023, 2023, 13889 : 209 - 220
  • [29] Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips)
    Wagner, Uli
    Welzl, Emo
    PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), 2020, : 2823 - 2841
  • [30] Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips)
    Wagner, Uli
    Welzl, Emo
    PROCEEDINGS OF THE 2020 ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2020, : 2823 - 2841
12345