Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • 05C  (1)
  • reachability  (1)
  • 1
    Electronic Resource
    Electronic Resource
    The Colin de Verdière number and sphere representations of a graph (1997)
    Springer
    Combinatorica 17 (1997), S. 483-521 
    Details
    ISSN: 1439-6912
    Keywords: 05C
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Colin de Vedière introduced an interesting linear algebraic invariant μ(G) of graphs. He proved that μ(G)≤2 if and only ifG is outerplanar, and μ(G)≤3 if and only ifG is planar. We prove that if the complement of a graphG onn nodes is outerplanar, then μ(G)≥n−4, and if it is planar, then μ(G)≥n−5. We give a full characterization of maximal planar graphs whose complementsG have μ(G)=n−5. In the opposite direction we show that ifG does not have “twin” nodes, then μ(G)≥n−3 implies that the complement ofG is outerplanar, and μ(G)≥n−4 implies that the complement ofG is planar. Our main tools are a geometric formulation of the invariant, and constructing representations of graphs by spheres, related to the classical result of Koebe about representing planar graphs by touching disks. In particular we show that such sphere representations characterize outerplanar and planar graphs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01195002
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Chip-Firing Games on Directed Graphs (1992)
    Springer
    Journal of algebraic combinatorics 1 (1992), S. 305-328 
    Details
    ISSN: 1572-9192
    Keywords: chip-firing game ; vector addition system ; reachability ; random walk ; probabilistic abacus ; Laplace operator ; Petri net
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider the following (solitary) game: each node of a directed graph contains a pile of chips. A move consists of selecting a node with at least as many chips as its outdegree, and sending one chip along each outgoing edge to its neighbors. We extend to directed graphs several results on the undirected version obtained earlier by the authors, P. Shor, and G. Tardos, and we discuss some new topics such as periodicity, reachability, and probabilistic aspects. Among the new results specifically concerning digraphs, we relate the length of the shortest period of an infinite game to the length of the longest terminating game, and also to the access time of random walks on the same graph. These questions involve a study of the Laplace operator for directed graphs. We show that for many graphs, in particular for undirected graphs, the problem whether a given position of the chips can be reached from the initial position is polynomial time solvable. Finally, we show how the basic properties of the “probabilistic abacus” can be derived from our results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1022467132614
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...