补图具有悬挂点且连通的图的最小特征值

图的最小特征值定义为图的邻接矩阵的最小特征值,它是刻画图的结构性质的重要参数.在给定阶数且补图为具有悬挂点的连通图的图类中,刻画了最小特征值达极小的唯一图,并给出了这类图最小特征值的下界.     

匹配数为2的图的最小特征值

在所有给定阶数且匹配数为2的连通图中,我们刻画了最小特征值达到极小的图,给出了这类图最小特征值的下界.     

4连通图的可去边与4连通图的构造

本文引进了４连通图的可去边的概念,,并证明了４连通图Ｇ中不存在可去边的充要条件是Ｇ＝Ｃ５或Ｃ６,同时给出了ｎ阶４连通图的一个新的构造方法．     

图的Laplace特征值

简要综述近年来图的Laplace特征值研究的一些进展，并提出若干尚待研究的问题。     

图的最小特征值（英文）

设图G是一个简单图,G的邻接矩阵用A(G)表示,A(G)的最小特征值λ_min(G)被称为G的最小特征值.首先建立了图的邻接矩阵的边数与最小特征值之间的关系,然后给出具有Hamiltonian路径或Hamiltonian圈的一些谱条件,或是Hamilton连通的,或是从每个顶点追踪到图的邻接矩阵的最小特征值.这为研究图的结构性质提供了一种行之有效的方法.     

上连通和超连通三次点传递图

图G称为上连通的,若对每个最小割集C,G-C有孤立点,G称为超连通的,若对每个最小割集C,G-C恰有两个连通分支,且其中之一为弧立点,本文刻划了上连通和超连通三次点传递图。     

最小次数至少为4的超欧拉图

设Ｇ是２－边－连通的ｎ阶图。假设对任何的的最小边割集Ｅ等于包含于Ｅ（Ｇ）且│Ｅ│≤３,Ｇ－Ｅ的每个分支的阶至少为ｎ／５,则或者Ｇ是一个超欧拉图或者Ｇ有５个互不相交的阶数为ｎ／５连通分支,当这５个分支都收缩时,Ｇ收缩为Ｋ２,３,这个结果推广了蔡小涛,Ｐ．Ａ．Ｃａｔｌｉｎ,Ｆ．Ｊａｅｇｅｒ和Ｈ．Ｊ．Ｌａｉ等人关于超欧拉图的结果。     

6连通图中的可收缩边

Kriesell(2001年)猜想：如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边．本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点，由此推出该猜想对κ=6成立。     

含有欧拉生成子图的3边连通图

本文所讨论的图均为无向、有限简单图。文中没有指明的记号、术语见[3]。图G的欧拉生成子图是一条经过G的所有顶点的闭迹,以下简称S-闭迹。     

3连通图的可去边数

设 e是 3连通图 G的一条边 ,如果 G- e是某个 3连通图的剖分 ,则称 e是 G的可去边 .本文给出了 3连通图的可去边数依赖于极大半轮的下界以及达到下界的极图 .     

Critical extreme points of the 2-edge connected spanning subgraph polytope

In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if is a non-integer minimal extreme point of P(G), then G and can be reduced, by means of some reduction operations, to a graph G' and an extreme point of P(G') where G' and satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the graphs for which the polytope P(G) is integral. Received: May, 2004 Part of this work has been done while the first author was visiting the Research Institute for Discrete Mathematics, University of Bonn, Germany.     

A tight lower bound on the maximum genus of 3-edge connected loopless graphs

1.IntroductionThernchmumgenusl7M(G),ofacormectedgraphG~(V,E)isthem~amongthegenera,amongwhichGhasacellularembeddingonaspherewithkhandles.SinceanyembeddingofGhasatleastonefaCe,byEulerpolyhedralequation,itcanbeobtainedthatwhereP(G)=IE(G)I--IV(G)l IisthecyclerankofG.AgraphGiscalledop-imbeddableif7M(C)=Lop]exactly.Kund.[1]provedthatthereareatleasttWOedge-disjointspanningtreesinGifGis4-edgecormected.LiuandXuongcharacterizedtheuptheeddabilityofgraphsasinthefollowing.Theorem1.112'31.Acorm…     

Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5≤k≤8 and n>k + 5) with the minimal least eigenvalue.     

非正则图的最大特征值

通过对图的最大特征分量与顶点度之间的关系的刻画,得到了图的谱半径与参数最大度和次大度之间的不等关系,进而获得了简单连通非正则图的谱半径的若干上界.     

On regular graphs and coronas whose second largest eigenvalue does not exceed 1

We characterize all regular graphs whose second largest eigenvalue does not exceed 1. In the sequel, we determine all coronas, different from cones, with the same property. Some results and examples regarding unsolved cases are also given.     

On perfectly two-edge connected graphs

This paper studies the graphs for which the 2-edge connected spanning subgraph polytope is completely described by the trivial inequalities and the so-called cut inequalities. These graphs are called perfectly 2-edge connected. The class of perfectly 2-edge connected graphs contains for instance the class of series-parallel graphs. We introduce a new class of perfectly 2-edge connected graphs. We discuss some structural properties of graphs which are (minimally with respect to some reduction operations) nonperfectly 2-edge connected. Using this we give sufficient conditions for a graph to be perfectly 2-edge connected.     

Finding 2-edge connected spanning subgraphs

This paper studies the NP-hard problem of finding a minimum size 2-edge connected spanning subgraph (2-ECSS). An algorithm is given that on an r-edge connected input graph G=(V,E) finds a 2-ECSS of size at most |V|+(|E|−|V|)/(r−1). For r-regular, r-edge connected input graphs for r=3, 4, 5 and 6, this gives approximation guarantees of and , respectively.     

The inverse eigenvalue problem for Hermitian matrices whose graphs are cycles

In 1979, Ferguson characterized the periodic Jacobi matrices with given eigenvalues and showed how to use the Lanzcos Algorithm to construct each such matrix. This article provides general characterizations and constructions for the complex analogue of periodic Jacobi matrices. As a consequence of the main procedure, we prove that the multiplicity of an eigenvalue of a periodic Jacobi matrix is at most 2.     

Augmenting the connectivity of geometric graphs

Let G be a connected plane geometric graph with n vertices. In this paper, we study bounds on the number of edges required to be added to G to obtain 2-vertex or 2-edge connected plane geometric graphs. In particular, we show that for G to become 2-edge connected, additional edges are required in some cases and that additional edges are always sufficient. For the special case of plane geometric trees, these bounds decrease to and , respectively.