摘要:

AbstractAvertex‐switching Gsof a graphGis obtained by deleting fromGall edges ofGwith exactly one end in the set of verticesS, and then adding toGall edges of the complement ofGwith exactly one end inS. We characterize the situations in whichGsis isomorphic toG, a result with application to the vertex‐switching reconstruction problem. We use these results to construct pairs ofvertex‐switching pseudosimilar vertices, nonsimilar verticesuandvin a graphGwithG{u}isomorphic toG{v}. We show that every such pair can be constructed by our me

ISSN:0364-9024    

DOI:10.1002/jgt.3190150602

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

年代:1991

数据来源: WILEY

摘要:

AbstractIn this paper, general results are presented that are related to ϕ‐tolerance intersection graphs previously defined by Jacobson, McMorris, and Mulder. For example, it is shown that all graphs are ϕ‐tolerance intersection graphs for all ϕ, yet for “nice” ϕ, almost no graphs are ϕ‐tolerance interval graphs. Additional results about representation of t

ISSN:0364-9024    

DOI:10.1002/jgt.3190150603

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

年代:1991

数据来源: WILEY

摘要:

AbstractFor a graphG, the cochromatic number ofG, denotedz(G), is the leastmfor which there is a partition of the vertex set ofGhaving orderm. where each part induces a complete or empty graph.We show that if {Gn} is a family of graphs whereGnhaso(n2log2(n)) edges, thenz(Gn) =o(n). We turn our attention to dichromatic numbers. Given a digraphD, the dichromatic number ofDis the minimum number of parts the vertex set ofDmust be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graphG, the dichromatic number ofG, denotedd(G), is the maximum dichromatic number of all orientations ofG.Letmbe an integer; byd(m) we mean the minimum size of all graphsGwhered(G) =m.We show thatd(m) = θ(m2ln2(m))

ISSN:0364-9024    

DOI:10.1002/jgt.3190150604

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe consider vertex‐transitive graphs embeddable on a fixed surface. We prove that all but a finite number of them admit embeddings as vertex‐transitivemapson surfaces of nonnegative Euler characteristic (sphere, projective plane, torus, or Klein bottle). It follows that with the exception of the cycles and a finite number of additional graphs, they are factor graphs of semiregular plane tilings. The results generalize previous work on the genus of minimal Cayley graphs by V. Proulx and T. W. Tucker and were obtained independently by C. Thomassen, with significant differences in the methods used. Our method is based on an excursion into the infinite. The local structure of our finite graphs is studied via a pointwise limit construction, and the infinite vertex‐transitive graphs obtained as such limits are classified by their connectivity and the number ofends.In two appendices, we derive a combinatorial version of Hurwitz's Theorem, and classify the vertex‐transitive maps on the Klein

ISSN:0364-9024    

DOI:10.1002/jgt.3190150605

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

年代:1991

数据来源: WILEY

摘要:

AbstractA harmonious coloring of a simple graphGis a coloring of the vertices such that adjacent vertices receive distinct colors and each pair of colors appears together on at most one edge. The harmonious chromatic numberh(G) is the least number of colors in such a coloring. We improve an upper bound onh(G) due to Lee and Mitchem, and give upper bounds for related quantities.

ISSN:0364-9024    

DOI:10.1002/jgt.3190150606

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe determine exactly the expected number of hamilton cycles in the random graph obtained by starting withnisolated vertices and adding edges at random until each vertex degree is at least two. This complements recent work of Cooper and Frieze. There are similar results concerning expected numbers, for example, of perfect matchings, spanning trees, hamilton paths, and directed hamilton cycles.

ISSN:0364-9024    

DOI:10.1002/jgt.3190150607

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

年代:1991

数据来源: WILEY

摘要:

AbstractIt is shown that the edges of a simple graph with a nowhere‐zero 4‐flow can be covered with cycles such that the sum of the lengths of the cycles is at most |E(G)| + |V(G)| −3. This solves a conjecture proposed by G

ISSN:0364-9024    

DOI:10.1002/jgt.3190150608

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

年代:1991

数据来源: WILEY

摘要:

AbstractA graph is said to have propertyP(k,l)(k⩾l) if for anyX∈ (Gk) there exists a cycle such that |X∩V(C)| =l.Obviously ann‐connected graph (n⩾ 2) satisfiesP(n,n). In this paper, we study parameterskandlsuch that everyn‐connected graph satisfiesP(k,l). We show that forr= 1 or 2 everyn‐connected graph satisfiesP(n+r,n). Forr= 3, there are infinitely many 3‐connected graphs that do not satisfyP(6,3). However, ifn⩾ max{3,(2r−1)(r+ 1)}, then everyn‐connected gr

ISSN:0364-9024    

DOI:10.1002/jgt.3190150609

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

年代:1991

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190150601

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

年代:1991

数据来源: WILEY