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 条

[41] Generalizing blocking semiovals in finite projective planes [J].

Crupi, Marilena ;

Ficarra, Antonino .

FINITE FIELDS AND THEIR APPLICATIONS, 2025, 108

[42] A Computationally Efficient Connectivity Index for Weighted Directed Graphs With Application to Underwater Sensor Networks [J].

Mahboubi, Hamid ;

Asadi, M. Mehdi ;

Blouin, Stephane ;

Aghdam, Amir G. .

IEEE ACCESS, 2022, 10 :54822-54832

[43] A note on connectivity of multi-agent systems with proximity graphs and linear feedback protocol [J].

Sun, Zhendong ;

Huang, Jie .

AUTOMATICA, 2009, 45 (08) :1953-1956

[44] On projective planes of type I-4 [J].

Bachmann O. .

Journal of Geometry, 2017, 108 (3) :885-898

[45] Isotopy and geotopy for ternary rings of projective planes [J].

Aschbacher, Michael .

JOURNAL OF ALGEBRA, 2008, 319 (02) :868-892

[46] Conic blocking sets in Desarguesian projective planes [J].

Holder L.D. .

Journal of Geometry, 2004, 80 (1-2) :95-105

[47] On the contour of graphs [J].

Artigas, D. ;

Dantas, S. ;

Dourado, M. C. ;

Szwarcfiter, J. L. ;

Yamaguchi, S. .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) :1356-1362

[48] The spum and sum-diameter of graphs: Labelings of sum graphs [J].

Li, Rupert .

DISCRETE MATHEMATICS, 2022, 345 (05)

[49] Classification of embeddings of the flag geometries of projective planes in finite projective spaces, part 3 [J].

Thas, JA ;

Van Maldeghem, H .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2000, 90 (01) :173-196

[50] Classification of embeddings of the flag geometries of projective planes in finite projective spaces, Part 2 [J].

Thas, JA ;

Van Maldeghem, H .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2000, 90 (02) :241-256

← 1 2 3 4 5 →