连通图的谱半径上界

图谱理论是图论研究的重要的领域之一.设图G是n阶简单连通图,具有n顶点和m条边的连通图,p(G)为图G的邻接矩阵的谱半径.利用代数的方法得出两个ρ(G)的上界为:■与■和达到上界的图.     

强正则图的一些性质

文[3]给出了强正则图的概念及有关性质,本文在此基地上利用图的谱性质,得到了强正则图的又一些性质。     

强正则图与Seidel变换

本文通过对图的Seidel变换进一步研究，得到了一些新的强正则图。     

非正则图的最大特征值

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

有向图的谱半径的二次度形式的上界

1 预备知识设D=D(V,E)为n 阶有向图(V 为顶点集,E 为弧集),其邻接矩阵A=A(D)= (α_(uv))_(n×n)的所有特征根:λ_1,λ2,…,λ_n 被称为有向图D 的邻接谱,简称谱.称(?){|λ_i|} 为D 的谱半径,记作ρ,ρ(D)或ρ(A).用d~-(u)和d~ (u)分别表示D 中顶点u 的入度和出度. 记V~-(u)={v}(v,u)∈E},V (u)={v|(u,v)∈E}.m~-(u)=1/((d~(u))(?)d~-(v), 称为D 中顶点u 的平均二次入度,m~ (u)=1/((d (u))(?)d~ (v),称为顶点u 的平均二次出度.其它有关术语可参考[1,2].     

强色指数的一个新的上界

给出了图的强色指数的一个新的上界，并指出几类恰好达到该上界的图，从而改进了Erodoes和Nesetri的强色指数猜想，在某种意义上证明了这个猜想。     

关于加权距离正则图和立方图

令G=(V,E)是简单的连通k-正则图;w_1相似文献   

距离正则图的推广

本文研究了直径为d(Γ) ≥ 2的距离正则图Γ的补图.利用Γ的交叉数分别证明了当d=2时,Γ的补图式强正则;当d ≥ 3时,Γ的补图是广义强正则.将文献[2]中的距离正则图Grassmann图、对偶极图、Hamming图推广到它们的补图,从而得到广义强正则图.     

关于3-正则图的路分解

本文讨论了3-正则图的路分解问题,证明了任意的3-正则图都有{P3,P4}分 解,其中Rk指包含k个顶点的路.     

最大2-正则诱导子图的长度

设G是2-连通图，c(G)是图G的最长诱导圈的长度，c′(G)是图G的最长诱导2-正则子图的长度。本文我们用图的特征值给出了c(G)和c′(G)的几个上界。     

Comment on “Kirchhoff index in line,subdivision and total graphs of a regular graph”

Let G$G$ be a connected regular graph. Denoted by t(G)$t\left(G\right)$ and Kf(G)$Kf\left(G\right)$ the total graph and Kirchhoff index of G$G$, respectively. This paper is to point out that Theorem 3.7 and Corollary 3.8 from “Kirchhoff index in line, subdivision and total graphs of a regular graph” [X. Gao, Y.F. Luo, W.W. Liu, Kirchhoff index in line, subdivision and total graphs of a regular graph, Discrete Appl. Math. 160(2012) 560–565] are incorrect, since the conclusion of a lemma is essentially wrong. Moreover, we first show the Laplacian characteristic polynomial of t(G)$t\left(G\right)$, where G$G$ is a regular graph. Consequently, by using Kf(G)$Kf\left(G\right)$, we give an expression on Kf(t(G))$Kf\left(t\left(G\right)\right)$ and a lower bound on Kf(t(G))$Kf\left(t\left(G\right)\right)$ of a regular graph G$G$, which correct Theorem 3.7 and Corollary 3.8 in Gao et al. (2012)  [2].     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

A family of regular graphs of girth 5

Murty [A generalization of the Hoffman-Singleton graph, Ars Combin. 7 (1979) 191-193.] constructed a family of (p^m+2)-regular graphs of girth five and order 2p^2m, where p?5 is a prime, which includes the Hoffman-Singleton graph [A.J. Hoffman, R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. (1960) 497-504]. This construction gives an upper bound for the least number f(k) of vertices of a k-regular graph with girth 5. In this paper, we extend the Murty construction to k-regular graphs with girth 5, for each k. In particular, we obtain new upper bounds for f(k), k?16.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

An improved upper bound for the TSP in cubic 3-edge-connected graphs

We consider the travelling salesman problem (TSP) problem on (the metric completion of) 3-edge-connected cubic graphs. These graphs are interesting because of the connection between their optimal solutions and the subtour elimination LP relaxation. Our main result is an approximation algorithm better than the 3/2-approximation algorithm for TSP in general.     

Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete.     

Upper bounds for independent domination in regular graphs

Let G be a regular graph of order n and degree δ. The independent domination numberi(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish upper bounds, as functions of n and δ, for the sum and product of the independent domination numbers of a regular graph and its complement.     

Note on upper bound graphs and forbidden subposets

In the upper bound graph of a poset P, the vertex set is V(P) and xy is an edge if there exists an m∈V(P) with x,y≤_Pm. We show some characterizations on split upper bound graphs, threshold upper bound graphs and difference upper bound graphs in terms of m-subposets and canonical posets.     

An improved upper bound on the density of universal random graphs

We give a polynomial time randomized algorithm that, on receiving as input a pair (H, G) of n‐vertex graphs, searches for an embedding of H into G. If H has bounded maximum degree and G is suitably dense and pseudorandom, then the algorithm succeeds with high probability. Our algorithm proves that, for every integer and a large enough constant C = C_d, as , asymptotically almost all graphs with n vertices and at least edges contain as subgraphs all graphs with n vertices and maximum degree at most d. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014