摘要:

AbstractThe set of different cycle lengths of a graphGis denoted byC(G). We study how the distribution ofC(G) depends on the minimum degree ofG. We prove two results indicating thatC(G) is dense in some sense. These results lead to the solution of a conjecture of Erdös and Hajnal stating that for suitable positive constantsa, bthe following holds:where δ(G) denotes the minimum degree of

ISSN:0364-9024    

DOI:10.1002/jgt.3190080402

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1984

数据来源: WILEY

摘要:

AbstractWe show that, forr= 1, 2, a graphGwith 2n+ 2 (≥6) vertices and maximum degree 2n+ 1 ‐ r is of Class 2 if and only if |E(G/v)|>( 22n+1) ‐rn, wherevis a vertex ofGof minimum degree, and we make a conjecture for 1 ≤r≤n, of which this result is a special case. Forr= 1 this result is due t

ISSN:0364-9024    

DOI:10.1002/jgt.3190080403

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1984

数据来源: WILEY

摘要:

AbstractA necessary condition for the decomposition of a treeTinto subtrees, each isomorphic to a tree from a given set of trees is presented. We also present a characterization of the set of trees for which the condition is sufficient. Many examples are given.

ISSN:0364-9024    

DOI:10.1002/jgt.3190080404

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1984

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190080405

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1984

数据来源: WILEY

摘要:

AbstractThere is diverse literature on various properties of a class of graphs known as circulants. We present a new result which answers the previously unsolved question of characterizing the connection sequence of circulants having point connectivity equal to point degree. We also develop some theorems regarding a new generalization of connectivity known as super‐connectivity. In addition, we give a survey of published results pertinent to the study of connectivity of circulant

ISSN:0364-9024    

DOI:10.1002/jgt.3190080406

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1984

数据来源: WILEY

摘要:

AbstractAn induced subgraphGof a graphHis a retract ofHif there is an edge‐preserving mapffromHontoGsuch thatf|Gis the identity map onG. A median graph is a connected graph such that for any three verticesu,vandw, there exists a unique vertexxwhich lies simultaneously on some shortest (u,v)‐, (v,w)‐, and (w,u)‐paths. It is shown that a graphGis a retract of some hypercube if and only ifGis a media

ISSN:0364-9024    

DOI:10.1002/jgt.3190080407

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1984

数据来源: WILEY

摘要:

AbstractThe main question addressed in this article is the following: Iftedges are removed from a (t+ 1) edge‐connected graphGhaving diameterD, how large can the diameter of the resulting graph be? (The diameter of a graph is the maximum, over all pairs of vertices, of the length of the shortest path joining those vertices.) We provide bounds on this value that imply that the maximum possible diameter of the resulting graph, for largeDand fixedt, is essentially (t+ 1) ·D. The bulk of the proof consists of showing that, iftedges areaddedto ann‐vertex pathPn, then the diameter of the resulting graph is at least (n/(t+ 1)) ‐ 1. Using a similar proof, we also show that iftedges are added to ann‐vertex cycleCn, then the least possible diameter of the resulting graph is (for largen) essentiallyn/(t+ 2) whentis even andn/(t+ 1) whentis odd. Examples are given in all these cases to show that there exist graphs for which the bounds are achieved. We also give results for the correspondingvertexdeletion problem for general graphs. Such results are of interest, for example, when studying the potential effects of node or link failures on the performance of a communication network, especially for networks in which the maximum time‐delay or signal degradation is directly related to the diameter of t

ISSN:0364-9024    

DOI:10.1002/jgt.3190080408

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1984

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190080401

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1984

数据来源: WILEY