摘要:

AbstractWe prove a theorem saying, when taken together with previous results of Bondy, Hemminger, and Thomassen, that every locally finite, infinite tree not containing a subdivision of the dyadic tree (i. e., the regular tree of degree 3) is uniquely determined, up to isomorphism, from its collection of vertex‐deleted subgraphs. Furthermore, as another partial result concerning the reconstruction of locally finite trees, we show that the same is true for locally finite trees whose set of vertices of degreesis nonempty and finite (for some positive integers

ISSN:0364-9024    

DOI:10.1002/jgt.3190050202

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

年代:1981

数据来源: WILEY

摘要:

AbstractIn this paper we report on the properties of the matching polynomial α(G) of a graphG. We present a number of recursion formulas for α(G), from which it follows that many families of orthogonal polynomials arise as matching polynomials of suitable families of graphs. We consider the relation between the matching and characteristic polynomials of a graph. Finally, we consider results which provide information on the zeros of α(

ISSN:0364-9024    

DOI:10.1002/jgt.3190050203

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

年代:1981

数据来源: WILEY

摘要:

AbstractWe obtain several sufficient conditions on the degrees of an oriented graph for the existence of long paths and cycles. As corollaries of our results we deduce that a regular tournament contains an edge‐disjoint Hamilton cycle and path, and that a regular bipartite tournament is hamiltonia

ISSN:0364-9024    

DOI:10.1002/jgt.3190050204

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

年代:1981

数据来源: WILEY

摘要:

AbstractWe prove that ifKis an undirected, simple, connected graph of even order which is of class one, regular of degreep≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graphGobtained fromKby splitting any vertex isp‐critical. We find that various constructions of critical graphs by S. Fiorini are special cases of a corollary of this res

ISSN:0364-9024    

DOI:10.1002/jgt.3190050205

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

年代:1981

数据来源: WILEY

摘要:

AbstractWe produce in this paper an upper bound for the number of vertices existing in a clique of maximum cardinal. The proof is based in particular on the existence of a maximum cardinal clique that contains no vertexxsuch that the neighborhood ofxis contained in the neighborhood of another vertexy.

ISSN:0364-9024    

DOI:10.1002/jgt.3190050206

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

年代:1981

数据来源: WILEY

摘要:

AbstractDissimilar vertices whose removal leaves isomorphic subgraphs are called pseudosimilar. We construct infinite families of graphs having identity automorphism group, yet every vertex is pseudosimilar to some other vertex. Potential impact on the Reconstruction Conjecture is considered. We also construct, for eachn, graphs containing a subset ofnvertices which are mutually pseudosimilar. the analogous problem for mutually pseudosimilar edges is introduced.

ISSN:0364-9024    

DOI:10.1002/jgt.3190050207

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

年代:1981

数据来源: WILEY

摘要:

AbstractIn this paper we discuss old and new theoretical methods for computing the number of graphs with a given partition. We also show how a judicious combination of these methods gives rise to a procedure that is sufficiently powerful to make possible the enumeration of all graphs on 10 points according to their partitions.

ISSN:0364-9024    

DOI:10.1002/jgt.3190050208

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

年代:1981

数据来源: WILEY

摘要:

AbstractA group Γ is said to be color ‐graph ‐hamiltonian if Γ has a minimal generating set Δ such that the Cayley color graphDΔ(Γ) is hamiltonian. It is shown that every hamiltonian group is color ‐graph

ISSN:0364-9024    

DOI:10.1002/jgt.3190050209

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

年代:1981

数据来源: WILEY

摘要:

AbstractA graph having 27 vertices is described, whose automorphism group is transitive on vertices and undirected edges, but not on directed edges.

ISSN:0364-9024    

DOI:10.1002/jgt.3190050210

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

年代:1981

数据来源: WILEY

摘要:

AbstractIn this Note it is proved that every connected, locally connected graph is upper embeddable. Moreover, a lower bound for the maximum genus of the square of a connected graph is given.

ISSN:0364-9024    

DOI:10.1002/jgt.3190050211

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

年代:1981

数据来源: WILEY