Super-connected edge transitive graphs

被引：8

作者：

Zhang, Zhao ^{[1
,2
]}

Meng, Jixiang ^{[1
]}

机构：

[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China

[2] Zhengzhou Univ, Dept Math, Zhengzhou 450052, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2008年 / 156卷 / 10期

基金：

中国国家自然科学基金;

关键词：

super-connected; edge transitive; reducible;

D O I：

10.1016/j.dam.2007.09.014

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles C-n (n >= 6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：1948 / 1953

页数：6