摘要:

AbstractWe prove that, in a random graph withnvertices andN=cnlognedges, the subgraph generated by a set of all vertices of degree at leastk+ 1 isk‐leaf connected forc>1/4. A threshold function fork‐leaf connectivity is also fo

ISSN:0364-9024    

DOI:10.1002/jgt.3190120102

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

年代:1988

数据来源: WILEY

摘要:

AbstractUsing the contraction method, we find a best possible condition involving the minimum degree for a triangle‐free graph to have a spanning eulerian subgrap

ISSN:0364-9024    

DOI:10.1002/jgt.3190120103

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

年代:1988

数据来源: WILEY

摘要:

AbstractLet

ISSN:0364-9024    

DOI:10.1002/jgt.3190120104

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

年代:1988

数据来源: WILEY

摘要:

AbstractWe ask, When does a graphGhave a subgraph Γ such that the vertices of odd degree in Γ form a specified setS⊆V(G), such thatG‐E(Γ) is connected? If such a subgraph can be found for a suitable choice ofS, then this can be applied to problems such as finding a spanning eulerian subgraph ofG. We provide a general method, with applic

ISSN:0364-9024    

DOI:10.1002/jgt.3190120105

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

年代:1988

数据来源: WILEY

摘要:

AbstractConsider the problem of determining the endpoints of an unknown edge x in a given graph G by asking questions of the form “Is vertexvan endpoint of edgeein G?”. Sharp upper and lower bounds are derived, and it is shown that determining the minimum number of questions in NP‐com

ISSN:0364-9024    

DOI:10.1002/jgt.3190120106

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

年代:1988

数据来源: WILEY

摘要:

AbstractAn algorithm for the construction of Ramsey graphs with a given automorphism groupGis presented. To find a graph onnvertices with no clique ofkvertices,Kk, and no independent set oflvertices, ¯Kl,k, l≤n, with an automorphism groupG, a Boolean formula α based on theG‐orbits ofk‐subsets andl‐subsets of vertices is constructed from incidence matrices belonging toG. This Boolean formula is satisfiable if and only if the desired graph exists, and each satisfying assignment to α specifies a set of orbits of pairs of vertices whose union gives the edges of such a graph. Finding these assignments is basically equivalent to the conversion of α from CNF to DNF (conjunctive to disjunctive normal form). Though the latter problem is NP‐hard, we present an “efficient” method to do the conversion for the formulas that appear in this particular problem. WhenGis taken to be the dihedral groupDnforn≤ 101, this method matches all of the previously known cyclic Ramsey graphs, as reported by F. R. K. Chung and C. M. Grinstead [“A Survey of Bounds for Classical Ramsey Numbers,”Journal of Graph Theory,7(1983), 25–38], in dramatically smaller computer time when compared to the time required by an exhaustive search. Five new lower bounds for the classical Ramsey numbers are established:R(4, 7) ⩾ 47,R(4, 8) ⩾ 52,R(4, 9) ⩾ 69,R(5,7) ⩾ 76, andR(5, 8) ⩾ 94. Also, some previously known cyclic graphs are s

ISSN:0364-9024    

DOI:10.1002/jgt.3190120107

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

年代:1988

数据来源: WILEY

摘要:

AbstractWe give a class of graphsGfor which there exists a homomorphism (= adjacency preserving map) fromV(G) toV(C), whereCis the shortest odd cycle inG, thereby extending a result of Albertson, Catlin, and Gibbons. Our class of graphs is characterized by the following property: For each odd subdivisionG′ ofGthere exists a homomorphic map fromV(G′) toV(C), whereC′ is the shortest odd cycle

ISSN:0364-9024    

DOI:10.1002/jgt.3190120108

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

年代:1988

数据来源: WILEY

摘要:

AbstractLetGbe a 2‐edge connected graph with at least 5 vertices. For any given verticesa, b, c, anddinGwitha≠b, there exists inG3a hamiltonian path with endpointsaandbavoiding the edgecd, and there exists inG3∪{cd}a hamiltonian path with endpointsaandband containing the edgecd.Also, after removal of two edges or one edge and one vertex fromG3, the resulting graph is still hamilt

ISSN:0364-9024    

DOI:10.1002/jgt.3190120109

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

年代:1988

数据来源: WILEY

摘要:

AbstractIf a graphGwith cycle rank ρ contains both spanning trees withmand withnend‐vertices,m

ISSN:0364-9024    

DOI:10.1002/jgt.3190120110

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

年代:1988

数据来源: WILEY

摘要:

AbstractWe say that a graph family ℱ has the Erdös‐Pósa property if there exists a functionf(k) such that any graphGcontains eitherkdisjoint subgraphs each isomorphic to a member of ℱ, or contains a setSof at mostf(k) vertices such thatG — Scontains no graph in ℱ. We derive a general sufficient condition for a family of graphs to have the Erdös‐Pósa property. In particular, for any fixed natural numbermthe collection of cycles of length divisible bymhas the Erdös‐Pósa property. As a by‐product, we obtain a polynomially bounded algorithm for finding a cycle of length divisible bym. On the other hand, we describe a general class of planar graphsHsuch that a collection of subdivisions ofHdoes not have the Erdös‐Pósa property. In

ISSN:0364-9024    

DOI:10.1002/jgt.3190120111

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

年代:1988

数据来源: WILEY