摘要:

AbstractMallows and Riordan “The Inversion Enumerator for Labeled Trees,”Bulletin of the American Mathematics Society, vol. 74 [1968] pp. 92‐94) first defined the inversion polynomial,Jn(q)for trees withnvertices and found its generating function. In the present work, we define inversion polynomials for ordered, plane, and cyclic trees, and find their values atq= 0, ± 1. Our techniques involve the use of generating functions (including Lagrange inversion), hypergeometric series, and binomial coefficient identities, induction, and bijections. We also derive asymptotic formulae for those results for which we do not have a closed form. © 1995 John Wiley&So

ISSN:0364-9024    

DOI:10.1002/jgt.3190190402

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The2‐intersection numberθ2(G) of a graphGis the minimum size of the union of sets in such a representation. We prove that the maximum order of a path that can be represented in this way usingtelements is between (t2‐ 19t+ 4)/4 and (t2‐t+ 6)/4, making θ2(Pn) asymptotic to 2√n. We also show the existence of a constantcdepending on ϵ such that, for any treeTwith maximum degree at mostd, θ2(T) ≤c(√n)1+ϵ. When the maximum degree is not bounded, there is ann‐vertex treeTwith θ2(T)>.945n2/3. © 1995

ISSN:0364-9024    

DOI:10.1002/jgt.3190190403

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe show that a directed graph of ordernwill containn‐cycles of every orientation, provided each vertex has indegree and outdegree at least (1/2 +n‐1/6)nandnis sufficiently large. © 1995 John Wiley&Sons,

ISSN:0364-9024    

DOI:10.1002/jgt.3190190404

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

年代:1995

数据来源: WILEY

摘要:

AbstractA digraph obtained by replacing each edge of a completem‐partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is calied a semicompletem‐partite digraph. We describe results (theorems and algorithms) on directed walks in semicompletem‐partite digraphs, including some recent results concerning tournaments. © 1995 John Wiley&Son

ISSN:0364-9024    

DOI:10.1002/jgt.3190190405

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

年代:1995

数据来源: WILEY

摘要:

AbstractIn 1965 Ringel raised a 6 color problem for graphs that can be stated in at least three different forms. In particular, is it possible to color the vertices and faces of every plane graph with 6 colors so that any two adjacent or incident elements are colored differently? This 6 color problem was solved in 1984 by the present author; the proof used about 35 reducible configurations. A shorter new proof is given here using only half as many of reducible configurations. © 1995 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190190406

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

年代:1995

数据来源: WILEY

摘要:

AbstractA λ‐coloring of a graph G is an assignment of λ or fewer colors to the points of G so that no two adjacent points have the same color. Let Ω (n,e) be the collection of all connected n‐point and e‐edge graphs and let Ωp(n,e) be the planar graphs of Ω(n, e). This paper characterizes the graphs that minimize the number of λ‐colorings in Ω(n, e) for all λ>1 and Ωp(n,e) for all λ.4. © 1995 Jo

ISSN:0364-9024    

DOI:10.1002/jgt.3190190407

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

年代:1995

数据来源: WILEY

摘要:

AbstractTheDepth First Search(DFS) algorithm is one of the basic techniques that is used in a very large variety of graph algorithms. Most applications of the DFS involve the construction of a depth‐first spanning tree (DFS tree).In this paper, we give a complete characterization of all the graphs in which every spanning tree is a DFS tree. These graphs are calledTotal‐DFS‐Graphs.We prove that Total‐DFS‐Graphs are closed under minors. It follows by the work of Robertson and Seymour on graph minors that there is a finite set of forbidden minors of these graphs and that there is a polynomial algorithm for their recognition. We also provide explicit characterizations of these graphs in terms of forbidden minors and forbidden topological minors. The complete characterization implies explicit linear algorithm for their recognition. In some problems the degree of some vertices in the DFS tree obtained in a certain run are crucial and therefore we also consider the following problem: LetG = (V,E) be a connected undirected graph where |V| =nand letdϵNnbe a degree sequence upper bound vector.Is there any DFS tree T with degree sequencedTthat violatesd(i.e.,dT≤d,which means: E jsuch thatdT(j)>d(j))? We show that this problem isNP‐completeeven for the case where we restrict the degree of only on specific vertex to be less than or equal to k for a fixed k ≥ 2 (i.e., d = (n ‐ 1, ⃛, n ‐ 1, k, n ‐ 1, ⃛, n ‐ 1)).

ISSN:0364-9024    

DOI:10.1002/jgt.3190190408

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

年代:1995

数据来源: WILEY

摘要:

AbstractA claw is an induced subgraph isomorphic to K1,3.The claw‐point is the point of degree 3 in a claw. A graph is called p‐claw‐free when no p‐cycle has a claw‐point on it. It is proved that for p ≥ 4, p‐claw‐free graphs containting at least one chordless p‐cycle are edge reconstructible. It is also proved that chordal graphs are edge reconstructible. These two results together imply the edge reconstructibility of claw‐free graphs. A simple proof of vertex reconstructibility of P4‐reducible graphs is also presented. © 199

ISSN:0364-9024    

DOI:10.1002/jgt.3190190409

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

年代:1995

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190190401

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

年代:1995

数据来源: WILEY