共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
谱半径前六位的n阶单圈图 总被引:1,自引:0,他引:1
郭曙光 《高校应用数学学报(A辑)》2003,18(4):480-486
恰含一个圈的简单连通图称为单圈图。Cn记n个顶点的圈。△(i,j,κ)记C3的三个顶点上分别接出i,j,κ条悬挂边所得的图,其中i≥j≥κ≥0.Sl^n-l记Cl的某一顶点上接出n-l条悬挂边所得到的图。△(n-4 1,0,0)记△(n-4,0,0)的某个悬挂点上接出一条悬挂边所得到的图。本文证明了:若把所有n(n≥12)阶单圈图按其最大特征值从大到小的顺序排列,则排在前六位的依次是S3^n-3,△(n-4,1,0),△(n-4 1,0,0),S4^n-4,△(n-5,2,0),△(n-5,1,1)。 相似文献
4.
The reciprocal complementary Wiener number of a connected graph G is defined as where V(G) is the vertex set, d(u,v|G) is the distance between vertices u and v, d is the diameter of G. We determine the trees with the smallest, the second smallest and the third smallest reciprocal complementary Wiener numbers, and the unicyclic and bicyclic graphs with the smallest and the second smallest reciprocal complementary Wiener numbers. 相似文献
5.
6.
7.
Jeff D. Kahn Nathan Linial Noam Nisan Michael E. Saks 《Journal of Theoretical Probability》1989,2(1):121-128
This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n
2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271. 相似文献
8.
In this paper, we determine the maximum number of maximal independent sets in a unicyclic connected graph. We also find a class of graphs achieving this maximum value. 相似文献
9.
Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index(AZI index) of a graph G, which is defined as AZI(G) =∑uv∈E(G)( d_u d_v/d_u + d_v-2)~3,where E(G) is the edge set of G, d u and d v are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest(resp., the first two smallest) AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively. 相似文献
11.
12.
For an integer , a graph is -hamiltonian if for any vertex subset with , is hamiltonian, and is -hamiltonian connected if for any vertex subset with , is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of -hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for , a line graph is -hamiltonian if and only if is -connected. In this paper we prove the following.(i) For an integer , the line graph of a claw-free graph is -hamiltonian if and only if is -connected.(ii) The line graph of a claw-free graph is 1-hamiltonian connected if and only if is 4-connected. 相似文献
13.
In our earlier paper [9], generalizing the well known notion of graceful graphs, a (p, m, n)-signed graph S of order p, with m positive edges and n negative edges, is called graceful if there exists an injective function f that assigns to its p vertices integers 0, 1,...,q = m + n such that when to each edge uv of S one assigns the absolute difference |f(u)-f(v)| the set of integers received by the positive edges of S is {1,2,...,m} and the set of integers received by the negative edges of S is {1,2,...,n}. Considering the conjecture therein that all signed cycles Zk, of admissible length k 3 and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths 0, 2 or 3 (mod 4) in which the set of negative edges forms a connected subsigraph. 相似文献
14.
设图\,$H(p,tK_{1,m})$\,是一个顶点数为\,$p+mt$\,的连通单圈图,它是由圈\,$C_{p}$\,的依次相邻的\,$t(1\leq t\leq p)$\,个顶点、每一个顶点分别与星\,$K_{1,m}$\,的中心重合而得到的单圈图. 证明了单圈图\,$ H( p,p K_{1,4})$, $H(p,p K_{1,3})$, $H(p,(p-1)K_{1,3})$\,是由它们的\,Laplacian\,谱确定的,并证明了当\,$p$\,为偶数时,单圈图\,$H(p,$2K_{1,3})$, $H( p,(p-2) K_{1,3})$, $H(p,(p-3)K_{1,3})$\,也是由它们的\,Laplacian\,谱确定的. 相似文献
15.
16.
Terry A. McKee 《Journal of Graph Theory》2000,33(3):151-160
Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationships between chordal and strongly chordal graphs and the previously studied families of chordal bipartite graphs, clique graphs of chordal graphs (dually chordal graphs), and incidence graphs of biacyclic hypergraphs. © 2000 John Wiley & Sons, Inc. J. Graph Theory 33: 151–160, 2000 相似文献
17.
Kenjiro Ogawa 《Discrete Mathematics》2010,310(22):3276-3277
For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,EU), where uv∈EU if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS2(G) is the graph with vertex set V(DS2(G))=V(G) and u,v∈V(DS2(G)) are adjacent if and only if dG(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. 相似文献
18.
A classical result of Komlós, Sárközy, and Szemerédi states that every n‐vertex graph with minimum degree at least (1/2 + o(1))n contains every n‐vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n‐vertex graph Gα with minimum degree at least αn for any fixed α > 0 and every n‐vertex tree T with bounded maximum degree, one can still find a copy of T in Gα with high probability after adding O(n) randomly chosen edges to Gα. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given and α > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n‐vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n‐vertex tree with maximum degree at most Δ. 相似文献
19.
A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. A graph G is called conservative if it admits an orientation and a labelling of the edges by integers {1,…,|E(G)|} such that at each vertex the sum of the labels on the incoming edges is equal to the sum of the labels on the outgoing edges. In this paper we deal with conservative graphs and their connection with the supermagic graphs. We introduce a new method to construct supermagic graphs using conservative graphs. Inter alia we show that the union of some circulant graphs and regular complete multipartite graphs are supermagic. 相似文献
20.