By Edward R. Scheinerman

"Both authors are first-class expositors-exceptionally so-and this makes for a gratifying learn and permits transparent realizing of the mathematical concepts." -Joel Spencer Fractional Graph idea explores some of the ways that integer-valued graph thought techniques may be changed to derive nonintegral values. in keeping with the authors' large overview of the literature, it presents a unified therapy of crucial ends up in the examine of fractional graph recommendations. Professors Scheinerman and Ullman start by way of constructing a normal fractional conception of hypergraphs and flow directly to supply in-depth insurance of basic and complex subject matters, together with fractional matching, fractional coloring, and fractional aspect coloring; fractional arboricity through matroid tools; and fractional isomorphism. the ultimate bankruptcy is dedicated to various extra concerns, equivalent to fractional topological graph concept, fractional cycle double covers, fractional domination, fractional intersection quantity, and fractional facets of in part ordered units. Supplemented with many not easy routines in each one bankruptcy in addition to an abundance of references and bibliographic fabric, Fractional Graph concept is a finished reference for researchers and a very good graduate-level textual content for college kids of graph idea and linear programming.

Show description

Read Online or Download Fractional Graph Theory: A Rational Approach to the Theory of Graphs PDF

Best graph theory books

Approximative Algorithmen und Nichtapproximierbarkeit

Jansen, Klaus. Approximative Algorithmen und Nichtapproximierbarkeit (de Gruyter, 2008)(ISBN 3110203162)(521s)

Nonlinear dimensionality reduction

This publication describes verified and complicated tools for decreasing the dimensionality of numerical databases. each one description begins from intuitive rules, develops the required mathematical information, and ends through outlining the algorithmic implementation. The textual content offers a lucid precis of proof and ideas in terms of famous equipment in addition to fresh advancements in nonlinear dimensionality aid.

Additional info for Fractional Graph Theory: A Rational Approach to the Theory of Graphs

Example text

Given an optimal fractional matching of G, we construct a maximum matching of B(G) of cardinality 2 e∈E(G) f (e). 1, there is a transversal of B(G) of the same cardinality. From this transversal, construct a fractional transversal g : V (G) → {0, 1/2, 1} of G by setting g(vi ) = 1 if both xi and yi are in the transversal, 1/2 if only one is, and 0 otherwise. The sum v∈V (G) g(v) is clearly half the cardinality of the transversal of B(G), namely, e∈E(G) f (e), which ✷ is equal to μf (G). Hence g is an optimal fractional transversal.

Then G is fractionally Hamiltonian if and only if the value of the fractional Hamiltonian LP is exactly ν(G). Proof. Exercise 7 on page 27. ✷ 22 Chapter 2. Fractional Matching Note that every edge cut in a fractional Hamiltonian cycle must have weight at least 2, but certain natural cuts must have weight exactly two. 2 Let f be a fractional Hamiltonian cycle for a graph G and let v be any vertex of G. Then f (e) = 2. e v Proof. Let v be any vertex and let S = {v}. Then f (e) ≥ 2. f (e) = e v e∈[S,S] To conclude, we compute 2ν(G) ≤ f (e) = 2 v∈V (G) e v f (e) = 2ν(G) e∈E(G) ✷ and the result follows.

This result remains true in the fractional case. 1 The join of graphs G and H, denoted G ∨ H, is formed by taking copies of G and H on disjoint sets of vertices and adding edges between every vertex of G and every vertex of H. 8 Let G be a graph without isolated vertices. Then kf (G) + μf (G) = ν(G). Proof. By duality, it is enough to show that pf (G) + τf (G) = ν(G). Choose f, g : V (G) → [0, 1] with g(v) = 1 − f (v). For any pair of vertices (but especially for uv ∈ E(G)) we have f (u) + f (v) ≥ 1 ⇐⇒ g(u) + g(v) ≤ 1.

Download PDF sample

Rated 4.64 of 5 – based on 32 votes