摘要:

AbstractWe obtain an upper bound on the expected number of regions in the randomly chosen orientable embedding of a fixed graph. This bound is ised to show that the average genus of the random graph onvvertices is close to its maximum genus. More specifically, it is proven that the difference between these two parameters is bounded by a function that is linear inv. These bounds are obtained in the context of permutation—partition pairs. © 1996 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190200102

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe following definition is motivated by the study of circle orders and their connections to graphs. A graphsGis called apoint‐halfspace graph(inRk) provided one can assign to each vertexvϵ (G) a pointpvRkand to each edgeeϵE(G) a closed halfspaceHeϵRkso thatvis incident witheif and only ifpvϵHe. LetHkdenote the set of point‐halfspace graphs (inRk).We give complete forbidden subgraph and structural characterizations of the classesHkfor everyk. Surprisingly, these classes are closed under taking minors and we give forbidden minor characterizations as well. © 1996 John Wiley&S

ISSN:0364-9024    

DOI:10.1002/jgt.3190200103

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe study the squares and the clique graphs of chordal graphs and various special classes of chordal graphs. Chordality conditions for squares and clique graphs are given. Several theorems concering chordal graphs are generalized. © 1996 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190200104

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

年代:1995

数据来源: WILEY

摘要:

AbstractA generalized Steinhaus graph of ordernand typesis a graph withnvertices whose adjacency matrix (ai,j) satisfies the relationwhere 2 ≦i≦n−1,i+s(i− 1 ≦j≦n,cr,i,jϵ {0,1} for all 0 ≦r≦s(i) −1 andcs(i)−1,i,j= 1. The values ofs(i) andcr,i,jare fixed but arbitrary. Generalized Steinhaus graphs in which each edge has probability ½ are considered. In an article by A. Blass and F. Harary [“Properties of Almost All Graphs and Complexes,”Journal of Graph Theory, Vol. 3 (1976), pp. 225–240], a collection of first‐order axioms are given from which any first‐order property in graph theory or its negation can be deduced. We show that almost all generalized Steinhaus graphs satisfy these axioms. Thus the first‐order theory of random generalized Steinhaus graphs is identical with the theory of random graphs. Quasi‐random properties of graphs are described by F. R. K. Chung, R. L. Graham, and R. M. Wilson, [“Quasi‐Random Graphs,”Combinatorica, Vol. 9 (1989), pp. 345–362]. We conclude by demonstrating that almost all generalized Steinhaus graphs obey Property 2 and hence all equivalent quasi‐r

ISSN:0364-9024    

DOI:10.1002/jgt.3190200105

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

年代:1995

数据来源: WILEY

摘要:

AbstractAfull graphonnvertices, as defined by Fulkerson, is a representation of the intersection and containment relations among a system ofnsets. It has an undirected edge between vertices representing intersecting sets, and a directed edge fromatobif the corresponding setAcontaisnB. We give a unified argument to show that asymptotically, almost all full graphs can be obtained by taking an arbitrary undirected graph in thenvertices, distinguishing a clique in this graph that need not be maximal, and then adding directed edges going out from each vertex in the clique to all vertices to which there is not already an existing undirected edge. © 1996 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190200106

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

年代:1995

数据来源: WILEY

摘要:

AbstractIn this paper we give a construction that produces exactly those graphs having maximum rectilinear crossing number equal to the subthrackle bound. We then prove a theorem characterizing these graphs in terms of proper circular‐arc graphs. © 1996 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190200107

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

年代:1995

数据来源: WILEY

摘要:

AbstractThis article shows that the vertices of a plane triangulation may be colored with 10 colors such that every pair of vertices has different colors if they are either adjacent or diagonal, that is, that they are not adjacent but are adjacent to two faces which share an edge. This improves a result of Borodin, who showed that 11 colors were sufficient. © 1996 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190200108

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe determine how much the bandwidthB(G) of a graphGcan increase when a single edge is added. Letg(b,n) be the maximum possible value ofB(G+e) whenGhasnvertices and bandwidthb. The problem of studying whenB(G+e) ≦B(G) + 1 was originally possed by Erdos. We determine© 1996 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190200109

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

年代:1995

数据来源: WILEY

摘要:

AbstractA (1,2)‐eulerian weightwof a grph is hamiltonian if every faithful cover ofwis a set of two Hamilton circuits. LetGbe a 3‐connected cubic graph containing no subdivition of the Petersen graph. We prove that ifGadmits a hamiltonian weight thenGis uniquely 3‐edge‐colorable. © 1996 John Wiley&S

ISSN:0364-9024    

DOI:10.1002/jgt.3190200110

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

年代:1995

数据来源: WILEY

摘要:

AbstractLetvbe an arbitrary vertex of a 4‐edge‐connected Eulerian graphG. First we show the existence of a nonseparating cycle decompositiion ofGwith respect tov. With the help of this decomposition we are then able to construct 4 edge‐independent spanning trees with the common rootvin the sam graph. We conclude that an Eulerian graphGis 4‐edge‐connected iff for every vertexrϵV(G) there exist 4 edge‐independent spanning trees with a common rootr. © 1996 John Wi

ISSN:0364-9024    

DOI:10.1002/jgt.3190200111

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

年代:1995

数据来源: WILEY