摘要:

AbstractThe bandwidth problem for a graphGis to label itsnverticesviwith distinct integersf(vi) so that the quantity max{|f(vi) −f(vi)| : (vivj) ∈E(G)} is minimized. The corresponding problem for a real symmetric matrixMis to find a symmetric permutationM'ofMso that the quantity max{|i−j| :m'ij≠ 0} is minimized. This survey describes all the results known to the authors as of approximately August 1981. These results include the effect on bandwidth of local operations such as refinement and contraction of graphs, bounds on bandwidth in terms of other graph invariants, the bandwidth of special classes of graphs, and approximate bandwidth algorithms for graphs and matrices. The survey concludes with a brief discussion of some problems related to ba

ISSN:0364-9024    

DOI:10.1002/jgt.3190060302

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

年代:1982

数据来源: WILEY

摘要:

AbstractLet {pk}k≥2,k≠4 be a sequence of non‐negative integers which satisfies 8 + Σk≥3(k— 4)pk= 0. Then there exists an integerp4such that there exists a 2‐connected planar graph with exactlypkk‐gons as faces for allk≥ 2. This paper determines all suchp4whenpk= 0 fork≥ 5 and determines that there is a constantC≥ 1 such that for somem≤p2+ 1/4p3+C, there exists a 2‐connected planar graph with exactlypkfaces for eachp4=m+ 2w,wa positive integer. When there exists at least one oddk≥ 3 for whichpk≠ 0, the coefficient 2 ofwin the above equation may be replaced by 1. These conclusions do not hold if the coefficients ofp2andp3are any smaller

ISSN:0364-9024    

DOI:10.1002/jgt.3190060303

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

年代:1982

数据来源: WILEY

摘要:

AbstractUsing generating functions and asymptotic techniques, the probability that in a large random tree a point is of degreerand an orbit of sizesforr≤ 7 ands≤ 7 is calculated. For example, it is found that about 17% of the points of a random tree are fixed and have degree one. This method is readily applied to different types of tr

ISSN:0364-9024    

DOI:10.1002/jgt.3190060304

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

年代:1982

数据来源: WILEY

摘要:

AbstractIn this article, we give the maximum number of arc‐disjoint arborescences in a tournament or an oriented completer‐partite graph by means of the indegrees of its verti

ISSN:0364-9024    

DOI:10.1002/jgt.3190060305

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

年代:1982

数据来源: WILEY

摘要:

AbstractThe number of tournamentsTnonnnodes with a unique spanning cycle is the (2n‐6)th Fibonacci number whenn≥ 4. Another proof of this result is given based on a recursive construction of these tourname

ISSN:0364-9024    

DOI:10.1002/jgt.3190060306

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

年代:1982

数据来源: WILEY

摘要:

AbstractGiven a setFof digraphs, we say a graphGis aF‐graph(resp.,F*‐graph) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs inF. It is proved that all the classes of graphs mentioned in the title areF‐graphs orF*‐graphs for subsetsFof a set of three d

ISSN:0364-9024    

DOI:10.1002/jgt.3190060307

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

年代:1982

数据来源: WILEY

摘要:

AbstractAn island decomposition of a graphGconsists of a set of vertex‐disjoint paths which cover the vertex set ofG.If the endpoints of the paths are mutually nonadjacent, then we have an atoll decomposition. We characterize graphs requiring two paths in an island decomposition yet having no atoll decomposition. Results are given relating atoll decompositions to cutpoints and Hamiltonian block

ISSN:0364-9024    

DOI:10.1002/jgt.3190060308

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

年代:1982

数据来源: WILEY

摘要:

AbstractLetC(v1, …,vn) be a system consisting of a circleCwith chordsv1, …,vnon it having different endpoints. Define a graphGhaving vertex setV(G)= {v1, …,vn} and for which verticesviandvjare adjacent inGif the chordsviandvjintersect. Such a graph will be called a circle graph. The chords divide the interior ofCinto a number of regions. We give a method which associates to each such region an orientation of the edges ofG.For a givenC(v1, …,vn) the numbermof different orientations corresponding to it satisfiesq+ 1 ≤m≤n+q+ 1, whereqis the number of edges inG.An oriented graph obtained from a diagramC(v1, …,vn) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation ofGis acyclic. In this case we define a special orientation of the complement ofG, and use this to develop an improved algorithm for finding a maximum indepe

ISSN:0364-9024    

DOI:10.1002/jgt.3190060309

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

年代:1982

数据来源: WILEY

摘要:

AbstractThe only uncontractable 4‐connected graphs areC2nforn≥ 5 and the line graphs of the cubic cyclically 4‐connected g

ISSN:0364-9024    

DOI:10.1002/jgt.3190060310

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

年代:1982

数据来源: WILEY

摘要:

AbstractIt is proved that a simple 4‐regular graph withoutK1,3as an induced subgraph has a 3‐regular subgr

ISSN:0364-9024    

DOI:10.1002/jgt.3190060311

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

年代:1982

数据来源: WILEY