ISSN:0364-9024    

DOI:10.1002/jgt.3190090302

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

年代:1985

数据来源: WILEY

摘要:

AbstractIt is well known that any spanning tree of a graph can be obtained from any other by a sequence of single edge exchanges in a way that preserves, at each step, the property of being a spanning tree. We consider a variation of this problem concerning pairs of edge‐disjoint spanning trees. In particular, it is shown that any pair of edge‐disjoint spanning trees can be obtained from any other by a sequence of single edge exchanges in a way that preserves, at each step, the property of being edge‐disjoint spanning

ISSN:0364-9024    

DOI:10.1002/jgt.3190090303

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

年代:1985

数据来源: WILEY

摘要:

AbstractWe give constructions of bipartite graphs with maximum Δ, diameterDonBvertices, such that for everyD≥ 2 the lim infΔ→∞B. Δ1‐D=bD>0. We also improve similar results on ordinary graphs, for example, we prove that limΔ→∞N· Δ−D= 1 ifDis 3 or 5. This is a partial answer to a

ISSN:0364-9024    

DOI:10.1002/jgt.3190090304

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

年代:1985

数据来源: WILEY

摘要:

AbstractLetdithe degree of theith vertex of a mutigraph and λijbe the number of edges between vertexiand vertexj.A multigraph is called nearly balanced if |di−di| ≤1 for alli≠i′ and |λij−λij| for alliand allj,j′ Let be the collection of all the multigraphs withvvertices and e edges. It is shown that for anyv, there is ane* such that if, then any nearly balanced graph in ζv, ehas more spanning trees than any non‐nearly‐bala

ISSN:0364-9024    

DOI:10.1002/jgt.3190090306

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

年代:1985

数据来源: WILEY

摘要:

AbstractWe present a hypergraph coloring algorithm and analyze its performance in spaces of random hypergrpahs. In these spaces the number of colors used by our algorithm isalmost surelywithin a small constant factor (less than 2) of the weak chromatic number of the hypergraph. This also establishes new upper and lower bounds for the weak chromatic number of uniform hypergraphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190090307

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

年代:1985

数据来源: WILEY

摘要:

AbstractWe prove that every finite regular digraph has an arc‐transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2‐arc‐transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex‐transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrixAthere exists an arc‐transitive digraphXsuch that the minimum polynomial ofAdivides that ofX. It follows that there exist arc‐transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matricesA, we construct a 2‐arc‐tra

ISSN:0364-9024    

DOI:10.1002/jgt.3190090308

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

年代:1985

数据来源: WILEY

摘要:

AbstractWe prove that any graph with maximum degreenwhich can be obtained by removing exactly2n‐ 1 edges from the joinK1+Kn, nisn‐critical. This generalizes special constructions of critical graphs by S. Fiorini and H. P. Yap, and suggests a possible extension of another general construction due to

ISSN:0364-9024    

DOI:10.1002/jgt.3190090309

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

年代:1985

数据来源: WILEY

摘要:

AbstractWe construct infinite sequences of non‐Hamiltonian graphs and use them to show that the shortness exponent (or, in some cases, the shortness coefficient) is less than one for many classes of 3‐connected planar graphs whose faces are all r‐gons and whose vertices are all p‐valent or q‐valent, where p

ISSN:0364-9024    

DOI:10.1002/jgt.3190090310

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

年代:1985

数据来源: WILEY

摘要:

AbstractA Halin graph is a plane graphH = T U C, whereTis a plane tree with no vertex of degree two and at least one vertex of degree three or more, andCis a cycle connecting the endvertices ofTin the cyclic order determined by the embedding ofT.We prove that such a graph onnvertices contains cycles of all lengthsl, 3 ≤ln, except, possibly, for one even valuemofl. We prove also that if the treeTcontains no vertex of degree three thenGis pancycli

ISSN:0364-9024    

DOI:10.1002/jgt.3190090311

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

年代:1985

数据来源: WILEY

摘要:

AbstractLet Γ be the set of finite, simple and nondirected graphs being not embeddable into the torus. Furthermore let>4be a partial order‐relation and M4(Γ) the minimal basis of Γ. In this paper we determine three graphs of M4(Γ) being embeddable into the projective plane and containing the subg

ISSN:0364-9024    

DOI:10.1002/jgt.3190090312

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

年代:1985

数据来源: WILEY