TAILIEUCHUNG - Báo cáo khoa học: The restricted arc-width of a graph

An arc-representation of a graph is a function mapping each vertex in the graph to an arc on the unit circle in such a way that adjacent vertices are mapped to intersecting arcs. The width of such a representation is the maximum number of arcs passing through a single point. The arc-width of a graph is defined to be the minimum width over all of its arc-representations. We extend the work of Bar´at and Hajnal on this subject and develop a generalization we call restricted arcwidth. Our main results revolve around using this to bound arc-width from below and to examine the effect of several graph operations. | The restricted arc-width of a graph David Arthur Department of Mathematics Duke University Durham NC 27708 USA Submitted Jun 26 2003 Accepted Oct 13 2003 Published Oct 23 2003 MR Subject Classifications 05C62 05C83 Abstract An arc-representation of a graph is a function mapping each vertex in the graph to an arc on the unit circle in such a way that adjacent vertices are mapped to intersecting arcs. The width of such a representation is the maximum number of arcs passing through a single point. The arc-width of a graph is defined to be the minimum width over all of its arc-representations. We extend the work of Barat and Hajnal on this subject and develop a generalization we call restricted arcwidth. Our main results revolve around using this to bound arc-width from below and to examine the effect of several graph operations on arc-width. In particular we completely describe the effect of disjoint unions and wedge sums while providing tight bounds on the effect of cones. 1 Introduction The notion of a graph s path-width first arose in connection with the Graph Minors project where Robertson and Seymour 3 introduced it as their first minor-monotone parameter. Since then applications have arisen in the study of chromatic numbers circuit layout and natural language processing. More recently Barát and Hajnal 2 proposed a variant on path-width that leads to the analagous concept of arc-width. Although it has not been as widely studied as path-width arc-width has similar applications and is an interesting and challenging problem in its own right. Informally we define an arc-representation of a graph to be a function mapping each vertex in the graph to an arc on the unit circle in such a way that adjacent vertices are mapped to intersecting arcs. The width of such a representation is the maximum number of arcs passing through a point. The arc-width of a graph is then defined to be the minimum width over all of its arc-representations. We illustrate .

• Báo cáo khoa học
• The restricted arc
• mathematical knowledge
• reports of mathematics
• mathematical works
• Even circuits
• prescribed clockwise parity
• presentation reports
• On a two sided
• Tur´an problem
• Path counting
• random matrix theory
• scientific reports
• scientific research
• Correspondence between
• algorithmic characterizations
• Finding Induced Acyclic
• Random Digraphs
• Nonexistence results
• Hadamard like matrices
• Dominance Order
• Graphical Partitions
• On the functions
• values in [α(G
• Two new criteria mathematical knowledge
• comparison in the Bruhat order
• Box With Translates
• Two Given Rectangular Brick
• Tight estimates
• eigenvalues
• regular graphs
• Science (in Latin Scientia
• meaning knowledge or understanding) is the efforts to implement the invention
• and increased knowledge of the human understanding of how the operation of the physical world surroundings
• Through controlled methods
• scientists use to observe the signs of expression or of the material and unusual nature to collect data
• analyze information to explain how it works
• there at the phenomenon of things
• One of the ways that test method to simulate natural phenomena under controlled conditions and tested ideas
• Knowledge in science is the total amount of information that has accumulated research
• The definition of science is accepted as common knowledge that science has been actively systematized
• Colored Pr¨fer codes
• k edge colored trees
• On the q analogue
• the sum of cubes
• Propagation
• mean degrees Dieter Rautenbach