围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径

图的谱半径和Laplacian谱半径分别是图的邻接矩阵和Laplacian矩阵的最大特征值.本文中,我们分别刻画了围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径达到最大时的极图.     

具有k个悬挂点的n阶单圈图的第二大谱半径的极图

设G为具有k个悬挂点的n阶单圈图,刘慧清等给出了这类图的最大谱半径的极图,本文得到了当k≥3时具有第二大谱半径的极图.     

恰有k个悬挂点的n阶双圈和三圈图的拟拉普拉斯谱半径

设k,n为两个确定的正整数.本文得到了当1≤k≤n-7时恰有k个悬挂点的n阶连通三圈图的最大拟拉普拉斯谱半径的唯一极图,也得到了当1≤k≤n-5时恰有k个悬挂点的n阶连通双圈图的最大拟拉普拉斯谱半径的唯一极图.     

不含三圈的k圈图的拟拉普拉斯和拉普拉斯谱半径

k圈图是边数等于顶点数加k-1的简单连通图.文中确定了不含三圈的k圈图的拟拉普拉斯谱半径的上界,并刻画了达到该上界的极图.此外,文中确定了拟拉普拉斯谱半径排在前五位的不含三圈的单圈图,排在前八位的不含三圈的双圈图.最后说明文中所得结论对不含三圈的k圈图的拉普拉斯谱半径也成立.     

Halin图的点着色算法

本文解决了Halin图的点色数问题,并给出了一个可在线性时间内对Halin图进行点着色的算法。     

外平面图和Halin图谱半径的上界

本文给出了平面图中的外平面图的谱半径的上界,ρ（Ｇ）≤３／２＋．改进了１９９３年,ＣａｏＤａｓｏｎｇ和 Ｖｉｎｃｅ Ａ关于外平面图的谱半径上界;然后给出了 Ｈａｌｉｎ图的谱半径的可达上界,并刻划了达到上界的极图 ρ（Ｇ）≤１＋,等式成立当且仅当 Ｇ≌ Ｗｎ（轮图）．     

双圈图的Laplace矩阵的谱半径

利用奇异点对的分类,得到了n阶双圈图的Laplace矩阵的谱半径的第二至第八大值,并且刻划了达到这些上界的极图.     

Halin图的Alon-Tarsi数

图G的Alon-Tarsi数,是指最小的k使得G存在一个最大出度不大于k-1的定向D满足G的奇支撑欧拉子图的个数不同于偶支撑欧拉子图的个数.通过分析Halin图的结构,利用Alon-Tarsi定向的方法确定了Halin图的Alon-Tarsi数.     

连通图的最小Laplace谱半径的排序

首先找出了具有最小Laplace谱半径的第2个至第5个n阶单圈图和具有最小Laplace谱半径的n阶双圈图.然后结合有关n阶树的最小Laplace谱半径的排序,给出了所有n阶连通图中Laplace谱半径最小的14个图,当n为偶数时,它们达到了所有佗阶连通图中Laplace谱半径最小的9个值(其中有并列的),而当n为奇数时,它们则达到了Laplace谱半径最小的8个值(其中有并列的).     

给定边连通度的图的最小距离谱半径(英文)

本文研究了边连通度为r的n阶连通图中距离谱半径最小的极图问题,利用组合的方法,确定了K(n-1,r)为唯一的极图,其中K(n-1,r)是由完全图K_(n-1)添加一个顶点v以及连接v与K_(n-1)中r个顶点的边所构成.上述结论推广了极图理论中的相关结果.     

Graphs with the second largest number of maximal independent sets

Let G be a simple undirected graph. Denote by (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erd?s and Moser raised the problem of determining the maximum value of among all graphs of order n and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most r cycles. In this paper we determine the second largest value of and xi(G) among all graphs of order n. Moreover, the extremal graphs achieving these values are also determined.     

The critical groups of the Peisert graphs

The critical group of a finite graph is an abelian group defined by the Smith normal form of the Laplacian. We determine the critical groups of the Peisert graphs, a certain family of strongly regular graphs similar to, but different from, the Paley graphs. It is further shown that the adjacency matrices of the two graphs defined over a field of order \(p^2\) with \(p\equiv 3\pmod 4\) are similar over the \(\ell \)-local integers for every prime \(\ell \). Consequently, each such pair of graphs provides an example where all the corresponding generalized adjacency matrices are both cospectral and equivalent in the sense of Smith normal form.     

On the disjoint paths problem

Using flow and matching algorithms to solve the problem of finding disjoint paths through a given node, and with a technique of Chekuri and Khanna, we give an approximation for the edge-disjoint paths problem in undirected graphs, directed acyclic graphs and directed graphs with edge capacity at least 2.     

Asymptotic approximation for the number of <Emphasis Type="Italic">n</Emphasis>-vertex graphs of given diameter

We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by Füredi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices.     

On the existence of self-complementary and non-self-complementary strongly regular graphs with Paley parameters

For p an odd prime, let \({{\mathcal A}_{p}}\) be the complete classical affine association scheme whose associate classes correspond to parallel classes of lines in the classical affine plane AG(2, p). It is known that \({{\mathcal A}_{p}}\) is an amorphic association scheme. We investigate rank 3 fusion schemes of \({{\mathcal A}_{p}}\) whose basis graphs have the same parameters as the Paley graphs \({P(p^{2})}\). In contrast to the Paley graphs, the great majority of graphs we detect are non-self-complementary and non-Schurian. In particular, existence of non-self-complementary graphs with Paley parameters is established for \({p \ge 17}\), with an analogous existence result for non-Schurian such graphs when \({p \ge 11}\). We demonstrate that the number of self-complementary and non-self-complementary strongly regular graphs with Paley parameters grows rapidly as \({p \to \infty}\).     

Locally triangular graphs and normal quotients of the <Emphasis Type="Italic">n</Emphasis>-cube

For an integer \(n\ge 2\), the triangular graph has vertex set the 2-subsets of \(\{1,\ldots ,n\}\) and edge set the pairs of 2-subsets intersecting at one point. Such graphs are known to be halved graphs of bipartite rectagraphs, which are connected triangle-free graphs in which every 2-path lies in a unique quadrangle. We refine this result and provide a characterisation of connected locally triangular graphs as halved graphs of normal quotients of n-cubes. To do so, we study a parameter that generalises the concept of minimum distance for a binary linear code to arbitrary automorphism groups of the n-cube.     

On the Metric Dimension of Imprimitive Distance-Regular Graphs

A resolving set for a graph \({\Gamma}\) is a collection of vertices S, chosen so that for each vertex v, the list of distances from v to the members of S uniquely specifies v. The metric dimension of \({\Gamma}\) is the smallest size of a resolving set for \({\Gamma}\). Much attention has been paid to the metric dimension of distance-regular graphs. Work of Babai from the early 1980s yields general bounds on the metric dimension of primitive distance-regular graphs in terms of their parameters. We show how the metric dimension of an imprimitive distance-regular graph can be related to that of its halved and folded graphs. We also consider infinite families (including Taylor graphs and the incidence graphs of certain symmetric designs) where more precise results are possible.     

Hom complexes and homotopy in the category of graphs

In this extended abstract we develop a notion of ×-homotopy of graph maps that is based on the internal hom associated to the categorical product. We show that graph ×-homotopy is characterized by the topological properties of the so-called Hom complex, a functorial way to assign a poset to a pair of graphs. Along the way we establish some structural properties of Hom complexes involving products and exponentials of graphs, as well as a symmetry result which can be used to reprove a theorem of Kozlov involving foldings of graphs. We end with a discussion of graph homotopies arising from other internal homs, including the construction of ‘A-theory’ associated to the cartesian product in the category of reflexive graphs. For proofs and further discussions we refer the reader to the full paper [Anton Dochtermann. Hom complexes and homotopy theory in the category of graphs. arXiv:math.CO/0605275].