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
  • 06A10  (2)
  • Menger's theorem  (1)
  • 1
    Electronic Resource
    Electronic Resource
    A Note on Maxflow-Mincut and Homomorphic Equivalence in Matroids (2000)
    Springer
    Journal of algebraic combinatorics 12 (2000), S. 295-300 
    Details
    ISSN: 1572-9192
    Keywords: matroids ; strong maps ; homomorphisms ; duality ; Menger's theorem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Graph homomorphisms are used to study good characterizations for coloring problems Trans. Amer. Math. Soc. 384 (1996), 1281–1297; Discrete Math. 22 (1978), 287–300). Particularly, the following concept arises in this context: A pair of graphs (A, B) is called a homomorphism duality if for any graph G either there exists a homomorphism σ : A → G or there exists a homomorphism τ : G → B but not both. In this paper we show that maxflow-mincut duality for matroids can be put into this framework using strong maps as homomorphisms. More precisely, we show that, if C k denotes the circuit of length k + 1, the pairs (C k , C k + 1) are the only homomorphism dualities in the class of duals of matroids with the strong integer maxflow-mincut property (Jour. Comb. Theor. Ser.B 23 (1977), 189–222). Furthermore, we prove that for general matroids there is only a trivial homomorphism duality.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1011268025029
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Random graphs and covering graphs of posets (1986)
    Springer
    Order 3 (1986), S. 245-255 
    Details
    ISSN: 1572-9273
    Keywords: 06A10 ; 60C05 ; Poset ; diagram ; covering graph ; random graph
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n -1+η(n) ,where η(n) is bounded away from 0, then there is a constant k 0〉0 such that, for a.e. G p , c(G p )≥k 0 n 1+η(n) .In other words, to make G p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n -1+η(n) , where η(n)→0, thenc(G p )=o(n 1+η(n) ), almost surely.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00400288
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Complexity of diagrams (1987)
    Springer
    Order 3 (1987), S. 321-330 
    Details
    ISSN: 1572-9273
    Keywords: 06A10 ; Poset ; diagram ; NP-completeness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A diagram is an undirected graph corresponding to the covering relation of a finite poset. We prove that three decision problems related to diagrams are NP-complete.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00340774
    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...