摘要:

AbstractIn this expository paper we discuss the critical graph conjecture and its eventual disproof by M.K. Goldberg and others.

ISSN:0364-9024    

DOI:10.1002/jgt.3190070202

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

年代:1983

数据来源: WILEY

摘要:

AbstractDefine a geodesic subgraph of a graph to be a subgraphHwith the property that any geodesic of two points ofHis inH. The trivial geodesic subgraphs are the complete graphsKn' n≧ 0, andGitself. We characterize all (finite, simple, connected) graphs with only the trivial geodesic subgraphs, and give an algorithm for their construction. We do this also for triangle‐free gra

ISSN:0364-9024    

DOI:10.1002/jgt.3190070203

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

年代:1983

数据来源: WILEY

摘要:

AbstractFor each pairs,tof natural numbers there exist natural numbersf(s,t)andg(s,t)such that the vertex set of each graph of connectivity at leastf(s,t)(respectively minimum degree at leastg(s,t))has a decomposition into sets which induce subgraphs of connectivity (respectively minimum degree) at leastsandt, respectively.

ISSN:0364-9024    

DOI:10.1002/jgt.3190070204

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

年代:1983

数据来源: WILEY

摘要:

AbstractWe prove a theorem on paths with prescribed ends in a planar graph which extends Tutte's theorem on cycles in planar graphs [9] and implies the conjecture of Plummer [5]asserting that every 4‐connected planar graph is Hamiltonian‐connec

ISSN:0364-9024    

DOI:10.1002/jgt.3190070205

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

年代:1983

数据来源: WILEY

摘要:

AbstractThe notions “series‐parallel” and “nonseparable” are shown to be logical converses of each other when formulated in a particular dual‐like fashion. Self‐dual circuit/cutset characterizations are given of series‐parallel and of series‐parallel no

ISSN:0364-9024    

DOI:10.1002/jgt.3190070206

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

年代:1983

数据来源: WILEY

摘要:

AbstractWe consider a randommbynbipartite tournament Tmnconsisting ofmnindependent random arcs which have a common probabilitypof being directed from thempart to thenpart. We determine the expected value and variance of the number of 4‐cycles inTmnand the probability thatTmnhas no cycles. An asymptotic expression for this probability is also given whenp= 1/2 andmandntend to infinit

ISSN:0364-9024    

DOI:10.1002/jgt.3190070207

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

年代:1983

数据来源: WILEY

摘要:

AbstractA valuation on a simple graphGis an assignment of labels to the vertices ofGwhich induces an assignment of labels to the edges ofG.β‐valuations, also called graceful labelings, and α‐valuations, a subclass of graceful labelings, have an extensive literature; harmonious labelings have been introduced recently by Graham and Sloane. This paper introduces sequential labelings, a subclass of harmonious labelings, and shows that any tree admitting an α‐valuation also admits a sequential labeling and hence is harmonious. Constructions are given for new families of graceful and sequential graphs, generalizing some earlier results. Finally, a conjecture of Frucht is shown to be wrong by exhibiting several graceful labelings of wheels in which the center label is larger than previously thought

ISSN:0364-9024    

DOI:10.1002/jgt.3190070208

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

年代:1983

数据来源: WILEY

摘要:

AbstractThe following interpolation theorem is proved: If a graphGcontains spanning trees having exactlymandnend‐vertices, withm

ISSN:0364-9024    

DOI:10.1002/jgt.3190070209

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

年代:1983

数据来源: WILEY

摘要:

AbstractThe girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair is proved and simple bounds for their smallest order are developed. Several infinite classes of such graphs are constructed and it is proved that two of these families consist of smallest graphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190070210

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

年代:1983

数据来源: WILEY

摘要:

AbstractThe number of nonseparable graphs onnlabeled points andqlines isu(n, q).In the second paper of this series an exact formula foru(n, n + k)was found for generalnand successive (small)k.The method would give an asymptotic approximation for fixedkasn → ∞. Here an asymptotic approximation tou(n, n + k)is found whenk = O(n1/2)and an approximation to logu(n, n + k)whenk<(1 ‐ ϵ)(1/3n)1/2. The problem of finding an approximation tou(n, q)when (q ‐ n)/n1/2 → + → andq/n‐ 1/2 logn‐ 1/2 log l

ISSN:0364-9024    

DOI:10.1002/jgt.3190070211

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

年代:1983

数据来源: WILEY