GRAPHS CHAPTER 1 Contents 1. 2. 3. 4.

GRAPHS CHAPTER 1 Contents 1. 2. 3. 4. Families of simple graphs Metric space. Valence, Grith and Cages

Isomorhpism, Matrices and Graph Invariants 5. Connectivity in Graphs 6. Subgraphs 7. Basic Operations of graphs 8. Advanced Operations on Graphs 9. Variations of Graphs 10. Graph Products 1. 2.

3. 4. 5. 6. 7. Factors and Factorizations Planar Graphs Graphs from Polyhedra Metric Space - Revisited Representations of Graphs

Edge-Colorings and Snarks Vertex Colorings 1. Families of Simple Graphs Graphs 1 a 2

c d 3 e b 4

Simple graph G=(V,E) V = V(G) ={1,2,3,4} vertices E = E(G) = {a,b,c,d,e} edges Edge a has endvertices 1 and 2. Vertices 1 and 2 are adjacent: 1 ~ 2. Simple Graph Definition: Graph X is composed of a set of

vertices V(X) endowed with an irreflexive symmetric relation ~ (adjacency). An unordered pair of adjacent vertices uv = vu forms an edge. The set of edges is denoted by E(X). Sometimes we write X = (V,E) or X(V,E). Cycle Cn on n vertices. 1 2

3 4 C4 V vertices of a regular n-gon E edges |V|=n |E|=n

Small Cycles C3 C5 C4 C6

Some cycles as drawn by VEGA. It makes sense to define cylces C1 (a loop) and C2 (parallel edges), that are NOT simple. C1 C2

Path Pn on n vertices. 1 P4 V vertices of polygonal line. E segments. The endpoints of the polygonal line are called

the endpoints of the path. For instance, 1 and 4 are the endpoints of the path on the left. |V|=n |E|=n-1 2 3

1 2 3 4 4 Complete graph on n vertices Kn.

1 2 3 4 K4 V vertices of a regular n-gon E n-gon edges and

diagonals. |V|=n |E|=n(n-1)/2 Complete Bipartite Graph on n+m vertices Kn,m. 1 2 V = U1 U2 , U1 U2 = ;

|U1| = m, |U2 | = n. E = U1 U2 3 4 K2,2 |V|=n + m |E|=n m

The Petersen Graph and its Generalizations G(n,k) Petersen graph G(5,2) is an example of a generalized Petersen graph G(n,k). V(G(n,k)) consists of ui, vi, i = 1,2, ..., n. Edges: ui ~ ui+1 ui ~ v i vi ~ vi+k

(Warning! Addition mod n) Examples of Generalized Petersen graphs G(10,2) Dodecahedron G(10,3) Desargues graph. G(8,3) Mbius-Kantor graph. G(6,2) Drer graph.

2. Metric space Metric Space Space V, with mapping d (distance):

d:V V R with the following properties: d(u,v) 0, d(u,v) = 0, iff u = v. d(u,v) = d(v,u) d(u,v) d(u,w) + d(w,v) is called a metric space with distance d. Example: Hamming Distance {0,1}n is a metric space if the distance between u and v is the number of components in which the two vectors differ.

E.g. d([0,0,0,1,0,1],[1,1,0,1,1,1]) = 3. d is called the Hamming distance. Hypercube Qn. Q1 Q2

Q3 Hypercube of dimension d is the graph Qn, with: V(Qn) = {0,1}n. u ~ v, if d(u,v) = 1. |V(Qn)| = 2n |E(Qn )|= n 2n-1

Q4 Q5 3. Valence, Girth and Cages Vertex Valence 1 a

2 c d 3 e

b 4

G = (V,E) V(G) ={1,2,3,4} E(G) = {a,b,c,d,e} the number of edges incident with vertex v is called the valence or degree of v: deg(v). deg(1) = deg(4) = 3, deg(2) = deg(3) = 2. a vertex of valence 1 is called a leaf, a vertrex of valence 0 is isolated.

(G) minimal valence. (G) maximal valence. Regular Graphs Graph G is regular (of valence k), if G) = G) = k. Examples: Regular graphs: Kn, Cn, Kn,n Nonregular graphs: Pn, n > 2, Kn,m, n m. 1-valent and 2-valent graphs have simple structure.

Trivalent graphs have a special name: cubic graphs. (See example on the left) Girth Girth g(G) of graph G is the number of vertices of the shortest cycle in G. If G has no cycles, its girth is infinite. Cages

Graph G is a g-cage, if the following holds: 1. Trivalent 2. Has girth g 3. Has the least number of vertices among the graphs satisfying 1 and 2. Exercises 3

N1. Determine the 3-cage. N2. Determine the 4-cage. N3. Determine the 5-cage. N4. Determine the 6-cage. 4. Isomorphism, Matrices and Graph Invariants

Incidence Matrix M(G). To G=(V,E) we associate a rectangular matrix M=M(G) with |V| rows and |E| columns: Mv,e = { 1 ... v is the endpoint of e

0 ... otherwise Incidence Matrix - Example 1 a 2

c d 3 e G=(V,E) VG ={1,2,3,4} EG = {a,b,c,d,e}

b 4 1 MG = 2 3 4 a

1 1 0 0 b 0 1 0 1

c 1 0 0 1 d 1 0 1 0

e 0 0 1 1 Handshaking Lemma In each graph G=(V,E) : 2 |E(G)| = v 2 V(G) deg(v),

The proof uses the so-called bookkeepers rule in the incidence matrix of graph G. Graph Invariant It is well-known that we associate numbers to mathematical objects in various ways. For instance: Determinant is assicated with a matrix, degree is associated with a polynomial, dimension is associated with a space, length is associated with a vector, etc. There are several numbers that can be associated with a graph. Such a number is usually called graph invariant. One

may argue that the main topic of graph theory is the study of graph invariants. In addition to numbers other objects may be graph invariants. Isomorphisms and Graph Invariants An isomorphism G) = H is a bijective mapping: : V(G) ! V(H). that preserves adjacency: u ~ v if and only if (u)~(v). A graph invariant is a property, (usually a

number), that is preserved under an isomorphism. Isomorphism - Exercises A C B D

N1. Determine an isomorphism between graphs A and B. N2. Determine an isomorphism between graphs C

and D. Adjacency Matrix A(G). To each graph G=(V,E) with V={1,2,3,...,n} we can associate the adjacency matrix A=A(G) as follows: Ai,j = { 1 ...

i~j 0 ... sicer Adjacency Matrix - Example 1 a

2 c d 3 e G=(V,E)

VG ={1,2,3,4} EG = {a,b,c,d,e} b 4 0 1 AG = 1 1

1 0 0 1 1 0 0 1

1 1 1 0 Adjacency Matrix is Not an Invariant The adajcency matrix is not an invariant. It depends on the numbering of vertices. The incidence matrix is not an invariant. It depends on the numbering of the vertices

and ordering of the edges. Some Graph Invariants |V(G)| = number of vertices |E(G)| = number of edges G) = minimal valence.

G) = maximal valence Invariants - Example 1 a 2 c

d 3 e b 4

|V(G)| = 4 |E(G)| = 5 G) = 2 G) = 3 5. Connectivity in Graphs Disjoint Union of Sets Let A and B be sets. By A t B we denote

the disjoiont union of A and B. If A B = ;, then A t B is simply the union of the two sets. Otherwise we defne formally A t B = A {0} [ B {1}. Disjoint Union of Graphs Let G and G be graphs. By G t G we denote the disjoiont union of graphs G and G. This means V(G t G) := V(G) t V(G) and E(G t G) := E(G) t E(G).

The Empty Graph Empty graph has no vertices and no edges. Connectivity in Graphs - Theory Graph G is connected, if and only if it cannot be written as a disjoint union of two non-empty graphs. Connectivity of Graphs - Practice Graph is connected, if we grab and shake

the model made of balls and strings, and nothing falls down to earth. (No knotting of strings is permitted!) Equivalence Relation . Let G be a graph. On V(G) define as follows: For any u,v 2 V(G) let u v, if and only if there exists a subgraph, isomorphic to a path with endpoints u and v. Proposition. is an equivalence relation on V(G).

Proof. Obviously reflexive and symmetric. Proof of transitivity Homework. Path Connectivity of Graphs G is connected by paths, if the equivalence relation has a single equivalence class. Trees A tree is a connected graph with no cycles There are several characterizations of tree,

such as: A tree is a connected graph with n vertices and n-1 edges. A tree is a connected graph that is no longer connected after removal of any edge. A tree is connected and cycle free. Bipartite Graphs A graph is bipartite, if the vertex set can be partitioned into two

bipartitions, say G and R, such that each edge has one endpoint in G and the other in R. The graph on the left is biparitite. Exercises 5 N1: Show that each Km,n. is bipartite. N2: Show that each Qn is bipartite. N3(*): Show that a graph is bipartite if and only if

it has no odd cycles. N4: Which generalized Petersen graphs G(n,k) are bipartite? N5: Prove that each tree is a bipartite graph. N6: Prove that X is bipartite, if and only if each of its components is bipartite. Homework 5 H1: Prove that the relation is transitive. H2: Prove that for finite graphs the notions of connectedness and path connectedness

coincide. 6. Subgraphs Subgraphs Graph H=(U,F) is a subgraph of graph G=(V,E), if U V and F E. Warning! It is important that (U,F) is indeed a graph! Each edge from F must have both of its endpoints in U.

Subgraphs - Example 1 a 2 c d 3

e b 4 G=(V,E) VG ={1,2,3,4} EG = {a,b,c,d,e} Let: U = {1,2,3}, W = {2,3,4}, F = {b}, P =

{a,d}. Then (U,P) and (W,F) are subgraphs while (U,F) and (W,P) are not. Subgraph Types

Open subgraph Induced subgraph Spanning subgraph Isometric subgraph Convex subgraph Open Subgraph Subgraph H=(U,F) of graph G=(V,E) is open, if each ede e 2 E has either both endpoints in U, or none.

Trivial Subgraph Subgraph H is trivial, if either H = , or H = G. Connected Component A minimal nontrivial open subgraph is called a connected component of G. By (G) we denote the number of connected components of graph G.

Distance in a Connected Graph Each connected graph G gives rise to a metric space (V,dG) for dG(u,v) being the length of a shortest path in G, from u to v. Distance Partition For a given graph G and a given vertex v we may define the k-th link: Vk := {u 2 V(G)| d(v,u) = k}. This defines a partition V = {V0,V1,...,Ve} , Vk ; of the vertex set V(G) = V0 t V1 t ... t Ve. The number e is called the excentricity of vertex v. The

maximum excentricity is called the diameter of graph. This partition is called the distance partition of G with respect to v. Clearly, V0 = {v}. k-connectedness Graph G with |V(G)| > k is k-connected, if the removal of any set S with |S| < k leaves a connected graph. Connectivity (G) of graph G is the largest k, such that G is still k-connected. Vertex v of graph G is a cut-vertex, if (G v) > (G ). A connected graph with no cut-vertex is called a block. 2-connectedness Theorem: The following claims are equivalent: Graph G is 2-connected, Graph G is a block, Any pair of vertices belongs to a common

cycle. Mengers Theorem Two paths in a graph with a common pair of end-vertices are internally disjoint, if they have no other vertex in common. Theorem: Graph is k-connected, if and only if there are k pair-wise internally disjoint paths between any two of its vertices.

Spanning Subgraph If H=(U,F) is a subgraph of G(V,E) and U = V, then H is called a spanning subgraph of G. Spanning Paths and Cycles A spanning subgraph is also called a factor. A spanning path in a graph is also called a hamilton path. A spanning cycle in a graph is also called a hamilton cycle.

Spanning Trees Each connected graph has a spanning tree. For finite graphs the proof is not hard: A connected graph which is not a tree must contain a cycle. Removing a single edge from a cycle does not destroy connectivity. We may continue to remove edges from cycles until there is no cycle left, i.e. we obtain a spanning tree. For infinite graphs this fact is equivalent to the axiom of choice.

How many spanning trees does the complete graph have? K3 has three spanning trees! Let t(G) denote the number of spanning trees in G. Theorem: t(Kn) = nn-2 Proof: Prfer code!

Induced Subgraph Graph H is an induced subgraph of graph G, if H is obtained from G by removing the vertices from V(G)-V(H).

An induced subgraph of G is determined by its vertrex set U V(G). If we want to distinguish the graph from its vertex set we denote the former by or, if we want to refer to the original graph by G|U. Example: P5 is an induced subgraph of C6. Isometric Subgraph

H=(U,F) is an isometric subgraph of graph G=(V,E), if the distances are preserved: For each u,v 2 U: dH(u,v) = dG(u,v). Interval IG(u,v) Let u, v 2 V(G) belong to the same connected component of G. By IG(u,v) we denote the interval with endpoints u and v. IG(u,v) is the graph, induced on the set of vertices belonging to some shortest path from u to v.

If there is no danger of confusion we can simplify notation: I(u,v). Convex Subgraph Graph H is a convex subgraph of G, if for every pair of vertices u and v from V(H) that belong to the same connected component of G, the interval IG(u,v) is a subgraph of H. Exercises 6-1

N1. Prove that G is connected if and only if it has no nontrivial open subgraphs. N2. Show that if G has a hamilton cycle it also contains a hamilton path. N3. Show that every graph that has a hamilton path is connected. N4. Construct a graph on 10 vertices that has no hamilton path. N5. Construct a graph on 10 vertices that has no hamiloton cycle but has a hamilton path. N6: Construct a graph on 10 vertices that has a hamilton cycle.

Exercises 6-2 N7. Prove the following: In a connected graph G there exsists at least one distance partition such that each k-link Vk is an independent set if and only if G is bipartite. N8. Let G and H be graphs. We say, that G is locally H if and only if for each vertex v 2 V(G) the first link is isomorphic to H. Find a graph that is locally P3. N9. Prove that K2,2,2 is locally C4. N10. Determine all graphs with diameter 1. N11. Use the result of N7 to show that if one distance partion has independent k-links then all of them have independent k-links.

N12. Use N11 to design an algorithm that will find a bipartition of a bipartite connected graph. Exercises 6-3 N13. Prove that each convex subgraph is an isometric subgraph. N14. Prove that each isometric subgraph is an induced subgraph. N15. Prove that each connected component is a convex subgraph. N16. Prove that the intersection of two induced subgraphs is an induced subgraph. N17. Prove that the intersection of two convex subgraphs is a

convex subgraph. N18. Determine all intervals of the cube Q3. Exercises 6-4 7 6 8 5

4 1 2 3 N19. For H G define the convex closure cvx(H) of H in G. Compute cvx(Pk) in Cn. N20. Prove that each interval I(a,b) is a

subgraph of cvx(a,b). N21. Determine all intervals in the graph G on the left. Find two vertices a and b of G that have I(a,b) cvx(a,b). N22. Prove that althouth the subgraph induced by any shortest path in G is isometric, there are intervals that are not isometric subgraphs. N23. Prove that each interval in a tree is a path. N24. Characterize graphs, with the property

that each interval is a path. Homework 6 H1. Let C be the shortest cycle in graph G. Show that C is an induced subgraph of G. H2. Determine all non-isomorphic intervals in Q4. H3. Find an isometric subgraph of Q3 that is not convex. 7. Basic Operations on Graphs

Basic Operations on Graphs Deletion of edges Deletion of vertices

Addition of edges Union Complement Join Deletion of Edges If G = (V,E) is a graph and e 2 E one of tis edges, then G - e := (V,E {e}) is a subgraph of G. In such a case we say that G-e is obtained from G by deletion of edge e.

Deletion of Vertices Let x 2 V(G) be a vertex of graph G, then G - x is the subgraph obtained from G by removal of x grom V(G) and removal of all edges from E(G) having x as an endpoint. G x is obtained from G by deletion of vertex x. Edge Addition Let G be a graph and (u,v) a pair of nonadjacent vertices. Let e = uv denot the new

edge between u and v. By G = G + uv = G + e we denote the graph obtained from G by addition of edge e. In other words: V(G) : = V(G), E(G) : = E(G) [ {e}. Graph Union Revisited If G and H are graphs we denote by G t H their disjoint union. Instead of G t G we write 2G.

Generalization to nG, for an arbitrary positive integer n: 0G := ;. (n+1)G := nG t G Example: Top row : C6 t K9 Bottom row: 2K3. Graph Complement The graph

complement Gc of a simple graph G has V(Gc) := V(G), but two vertices u and v are adjacent in Gc if and only if they are not adjacent in G. For instance C4c is isomorphic to 2K2. Graph Difference

If H is a spanning subgraph of G we may define graph difference G \H as follows: V(G\H) := V(G). E(G\H) := E(G)\E(H). G H

G\H Bipartite Complement X Xb For a bipartite graph X (with a given

biparitition) one can define a bipartite complement Xb. This is the graph difference of Km,n and X: Xb = Km,n \ X. Empty Graph Revisited. The word empty graph is used in two meanings. First Meaning: ;. No vertices, no edges.

Second Meaning: En := Knc.= nK1. There are n vertices, no edges. E0 = ; = 0. G will be called the void graph or zero graph. Graph Join Join of graphs G and H is denoted by G*H and defined as follows: G*H := (Gc t Hc )c In particular, this means that Km,n is a join of two empty graphs En and Em.

Exercises 7 N1. Show that for any set F E(G) the graph G-F is well-defined. N2. Show that for any set X V(G) the graph GX is well-defined. N3. Show that for any set X V(G) and any set F E(G) the graph G-X-F is well-defined. N4. Prove that H is a subgraph of G if and only if H is obtained from G by a succession of vertex and edge deletion.

8. Advanced Operations on Graphs Cone and Suspension The join of G and K1 is called the cone over G and is denoted by Cone(G) = G*K1. The join G*(2K1 ) is called suspension. Examples Any complete multipartite graph is a join of empty graphs.

The cone Cone(Cn) is called a pyramid or wheel Wn. The octahedral graph is the suspension over C4. It can be written in the form: O3 = (2K1)*(2K1)*(2K1). Construction can be generalized to: On = (2K1)*(2K1)* ...*(2K1) Subdivision Let e 2 E(G) be an edge of G. Let S(G,e) denote the graph

obtained from G by replacing the edge e by a path of length 2 passing through a new vertex. Such an operation is called subdivision of the edge e.. Let F be a subset of E(G), then S(G,F) denotes the graph obtained from the subdivision of each edge of F. In the case F = E, we drop the second argument and S(G) denotes the subdivision graph of G. Graph H is a general subdivision of graph G, if H is obtained from G by a sequence of edge subdivisions. Graph Homeomorphism

Graphs G and H are homeomorphic, if they have a common subdivision. Graph G is topologically contained in a graph K, if there exists a subgraph H of K, that is homeomorphic to G. Matching Edges with no common endvertex are called independent. A set of pairwise independent edges is called a matching. Maximal Matching

A matching that cannot be augmented by adding new edges is called a maximal matching. Perfect Matching Proposition: Let M be a matching of a graph G on n vertices. Then |M| n/2. A matching M with |M| = n/2 is called a perfect matching. Abstract Simplicial Complex

a d b c e h

f g K P(S) is an abstract simplicial complex if for each 2 K and each it follows that 2 K. On the left:

K = {;, a, b, c, d, e, f, g, h, ab, ad, abd, bc, be, bce, bd, ce, df, dg, de, eh} Line Graph L(G) Two edges with a common end-vertex are incident. Incidence is a binary relation on the edge set E(G). Line graph L(G) has the vertex set E(G), while the edges of L(G) are determined by

the incidence of edges in G. Examples The top row depicts the Heawood graph and its fourvalent linegraph. The bottom row depicts the Petersen graph and its line graph.

Exercises 8-1 N1: Prove that for any graph X at least one of the graphs X and Xc is connected. N2: Decribe two graphs G and H, so that H is isomorphic to an induced subgraph, and also to a non-induced subgraph of G.

N3: The graph of our original example is isomorphic to K4-e. 1. 2. 3. 4. How many subgraphs does K4-e have? How many subgraphs of K4-e are non-isomorphic ? How many induced subgraphs does K4-e have ? How many of the induced subgraphs of K4-e are non-isomorphic?

Exercises 8-2 N4. Determine the number of vertices and egdes of the generalized octahedral graph On. N5. Let V = {-1,1}n. Define a graph Gn, whose vertex set is V and two vertices are adjacent if and only if d(u,v)2 < n. Prove that Gn is isomorphic to On. N6. Explore the relationship between graphs G1 = G * (2K1) and G2 = ((G*K1)*K1). N7. True or False? The Cone(H) is convex in Cone(G) if H is convex in G. N8. Show that G\H is a spanning subgraph of G. Exercises 8-3 N9: Prove that S(G) is bipartite for any simple G. N10: Find a general subdivision of K3,3 in G(5,2). N11: Given a graph X with n vertices and m edges. Determine the number of verticexs and the number of edges of S(X)? N12: Graph G is topologically almost contained in graph K, if there exists a subgraph H of K, that is a general subdivision of G. Prove that topological containment implies topological almost containment

and find a counterexample for the converse. Exercises 8-4 N13. Prove that |M| n/2 for any matching. N14. Prove that if a graph has a perfect matching then it has an even number of vertices. N15. Prove that a parfect matching is a maximal matching. Give an example of a maximal matching that is not perfect. N16. Show that the family of matchings defines an abstract simplicial complex on E(G).

Exercises 8-5 N17: Find a perfect matchning in the Petersen graph G(5,2). N18: Find a cubic graph with no perfect matching. Exercises 8-6 N19: Show that the line graph of a regular graph is regular. N20: What is the number of vertices and the number of edges of L(G), given the number of vertices n and the

number of edges m in G? N21: The trunacation T(G) of G is defined by T(G) := L(S(G)). What is the number of vertices (edges) in T(G)? N22: Draw T(K4) and T(Q3). N23: Define operations L(G) and T(G) only partially, for some set of vertices or edges, similarly to the definition of S(G,F). For instance, for bipartite graphs we may define operations with respect to only one bipartition set. Homework 8 H1. Prove that C8 is isomorphic to its bipartite

complement C8b. H2. Determine all paths Pn that are isomorphic to their bipartite complements Pnb. H3. Draw the suspension over C5. H4. A graph which is isomorphic to its complement is called self-complementary. Prove that there exists no selfcomplementary graph on (n+2) vertices, if there exist selfcomplementary graphs on n and on (n+1)-vertices. H5. Draw all self-complementary paths and all selfcomplementary cycles. 9. Variations of Graphs Variations of Graphs

Our main topic are simple finite graphs. We have to be aware of other similar creatures. Infinite graphs Digraphs

General graphs (multigraphs) Pregraphs Rooted graphs ... Infinite Graphs An infinite graph may have an infinite set of vertices or edges. Countable graphs have both sets coutable (or finite) Among countable graphs most tractable are locally finite graphs. (Each vertex has finite

valence). Even more restricted are bouded valence graphs, where (G) is finite, in particular regular ones. Examples Examples of infinite graphs: Each metric space (X,d) determines a unit distance graph: V(X) := X x ~ y , d(x,y) = 1.

Ray or infinite path P1 Double ray or infinite cycle C1 Infinite k-way tree T(1,k). Infinite square lattice Q1. Infinite triangular lattice T1.

Infinite hexagonal lattice H1. Digraphs In case of directed graphs (digraphs) there are no undirected edges e = uv, but there are directed edges or arcs: a = (u,v). u e = uv v

u a = (u,v) v Digraphs from Binary Relations Let R V V be a binary realtion on V. R defines a digraph in a natural way.

Loops, parallel edges, multigraphs A multigraph (general graph) is more general than a simple graph, since it may have parallel edges (between vertices u and v we may have two edges e = uv and f = uv) or loops. A loop z = uu is an edge whose endpoints coincide. u v

C2, parallel edges u C1, loop Dipoles, bouquets of circles and more 3 B4 The handcuff graph G(1,1)

Among general graphs there are several interesting families. A dipole n has two vertices and n parallel edges between them. A bouqet of circles Bn has one vertex with n loops. The handcuff graph G(1,1) is a graph with two

adjacent vertices, each one having a loop. Pregraphs If we want to distinguish a loop from a halfedge we need the notion of a pregraph. Definition of pregraph Pregraph X = (V,S,i,r) consists of

vertex set V, set of semi-edges S, mapping intial vertex, i: S ! V involution reverse r: S ! S. Since r is an involution, we have r2 = 1. The orbits of r of length 2 are edges, while orbits of length 1 are half-edges (semi-edges). A pregraph without half-edges is a general graph.

Rooted Graphs Let X be a graph and let r 2 V(X) be a selected vertex. A pair (X, r) is called a rooted graph and x is called the root. The idea of root can be generalized to a set of vertices or even a subgraph Y X. In some computer systems the root graph Y corresponds to the selected part of X. The idea can be generalized to graduated graphs:

Y0 = r Y1 ... Yk = X. Edge Contraction Let e = uv be an edge of G. By G/e we denote the graph obtained from G by contraction of e. This means we identify vertices u and v, remove the loop and identify possible extra parallel edges. Exercises 9-1 N1: Following the definion of a category, define a

digraph as a quadruple (V,A,i,t), where i and t are mappings, that assign to each arc a its intial vertex i(a) and terminal vertex t(a). Explain the procedure that starts with a binary relation R and obtains a digraph (V,A,i,t). N2: Define homomorphisms and isomorphisms of digraphs. N3: Formally define a directed path Pn!, directed cycle Cn! and directed complete graph Kn!. Exercises 9-2

N4: Describe a digraph that does not arise from a binary relation.. N5: Decribe a procedure that assings to each simple undirected graph (V,~) a directed graph in such a way that each undirected path is assigned a pair of oppositely directed arcs. N6: Prove that K5 can be obtained from G(5,2) by a series of edge contractions. 10. Graph Products

Graph Products For two graphs G and H we may define several graphs on the vertex set V(G) V(H) that behave like a product. The most natural one is the so-called Cartesian product that we introduce first. Square Grid Gr(n,m). Let Gr(n,m) denote the graph defined by a square grid in the plane, determined by n m nodes. We will call it a square grid. For instance,

Gr(2,2) is isomorphic to C4. We may regard Gr(n,m) as a product of paths Pn and Pm. In a similar way we may regards the n-prism graph as the product of a cycle Cn and K2. This is a motivation for the introduction of the Cartesian product of graphs. Cartesian Product of Graphs The Cartesian product , G H, of graphs G and H has vertex set VG VH and two vertices (u,v) and (u,v) are adjacent if and only if:

u = u and v ~ v or u ~ u and v = v. More products. The cartesian product is not the only product for graphs. If we define a category of graphs and dimension preserving maps, the categorical product is the so-called tensor product. If, however, the category admits also graph mappings that may map edges to vertices, the categorical product is the so-called strong product. We will

meet both of them. Tensor Product of Graphs The tensor product G H of graphs G and H has vertex set VG VH. Two vertices (u,v) and (u,v) are adjacent if and only if: u ~ u and v ~ v. Strong Product of Graphs The Strong product G H of graphs G and H has the vertex set VG VH. Two vertices (u,v)

and (u,v) are adjacent if and only if: u ~ u and v ~ v or u = u and v ~ v or u ~ u and v = v. Examples of Products P5 P4 P5 P4

P5 P4 On the left, there are cartesian, tensor and strong products of P5 by P4. [Cartesian product is the grid.] Exercises 10

N1: Let the graph Gi have ni vertices and mi edges, for i = 1,2. Determine th number of vertices and edges in their Cartesian product G 1 G2. N2: Let the graph Gi have ni vertices and mi edges, for i = 1,2. Determine the number of vertices and edges in their tensor product product G 1 G2.

N3: Let the graph Gi have ni vertices and mi edges, for i = 1,2. Determine the number of vertices and edges in their strong product G 1 G2. N4: Under what conditions will the Cartesian product G 1 G2 be connected? N5: Under what conditions will the tensor product G 1 G2 be connected? N6: Under what conditions will the strong product G 1 G2 be connected? N7: Under what conditions will the Cartesian product G 1 G2 be bipartite? N8: Under what conditions will the tensor product G 1 G2 be bipartite? N9: Under what conditions will the strong product G 1 G2 be bipartite? 11. Factors and Factorizations

Factors A spanning subgraph is also called a factor. A kvalent regular factor is simply called a k-factor. 1-factor is a different name for perfect matching. A 2-factor is a disjoint union of cycles covering the vertex set of the graph. Factorization Let G = (V,E) be a graph and let E be the disjoint union of sets E = F1 t F2 t ... t Fs, then Hi = (V,Fi) are factors of G and the decompostion of G into these factors is called a factorization. This is

written as: G = H1 H2 ... Hs If all factors Hi are k-factors, we speak of kfactorization of graph G. Example. For any graph G and any of its spanning subgraphs H we have the factorization: G = H G\H. Graph Power For a connected graph G and an integer k,

we define the k-th graph power G(k) as follows: V(G(k)) := V(G). u ~ v if and only if d(u,v) k. Pure Graph Power For a connected graph G and an integer k, we define the k-th pure graph power G [k] as follows: V(G[k]) := V(G). u ~ v if and only if d(u,v) = k.

Intermezzo - Partitions, Set Partitions, Graduated sets, etc.

Equivalence relation Set Paritition Distance Partition Ordered Set Partition Graduated Graph Graduated Set Valence Sequence (Number) Partition Hierarchy Nested (Graduated) Set Partitions Rooted Tree, Rooted Graph... MINIVEGA should support all these structures. Exercises 11-1 N1. Prove: If a trivalent graph contains a 1factor, it also has a 2-factor. N2. Find a trivalent graph, without a 1factor.

Exercises 11-2 N3: Prove that only regular d-valent graphs with d divisible by k admit a k-factorization. N4: Prove that non-regular graphs have no 1-factorizations. N5: Show that a 2-valent graph G has a 1-factorziation, if and only if it is the disjoint union of even cycles. N6: Prove that each prism n has a 1-factorization. N7. Prove that the Petersen graph has no 1-factorization. N8. Show that each cubic hamiltonian graph has a 1factorization.

Exercises 11-3 N9. Prove that for any integer k and connected graph G on n vertices we have: G(k) := G[0] = En. G(k) = G[0] G[1] ... G[k]. Homework 11 H1. Prove that each prism graph n = K2 Cn admits a 1-factorization. H2. Prove that each of the three products (cartesian, tensor, strong) is associative and

commutative (up to isomoprhism). H3. Give a definition of the following infinite graphs (a suitable drawing suffices): P1, C1, T(1,k), Q1,T1, H1, 12. Planar Graphs Planar Graphs Graph G is planar, if

it can be properly drawn in the plane. In order to explain this informal notion we have to define embeddings of graphs. Embeddings

Let be a nice topological space such as a metric space. An embedding of a general graph :G is defined as follows: 1. Injective mapping :V(G) 2. Family of continuous mappings e:[0,1] for each edge e = uv so that e( 0) = (u) and e(1) = (v). 3. In the interior of the interval e is injective and 4. its image contains no point that is an image of some other vertex or edge.

A connected component of (G) is called a face of the embedding. Graph G is planar, if it can be embedded in the plane. Stereographic Projection N T0 T1 There is a homeomorphic mapping of a sphere without the north pole N to

the Euclidean plane R2. It is called a stereographic projection. Take the unit sphere x2 + y2 + z2 = 1 and the plane z = 0. The mapping p: T0(x0,y0,z0) T1(x1,y1) is shown on the left.

Stereographic Projection N T0 T1 The mapping p: T0(x0,y0,z0) T1(x1,y1) is shown on the left. r1 = r0/(1-z0)

x1 = x0/(1-z0) y1 = y0/(1-z0) Example Take the Dodecahedron and a random point N on a sphere. The associated stereographic projection is depicted

below. Example A better strategy is to take N to be a face center as shown on the left. Eulers formula for planar graphs For a connected plane graph G with v vertices, e edges and f faces we have:

v e + f = 2. Warning: the outer face is counted! Farys Theorem Each simple planar graph admits a specially nice embedding. Theorem (Fary): Each simple planar graph can be embedded in the plane in such a way that all edges are represented by straight line segments.

Kuratowskis Theorem Theorem (Kuratowski): Graph G is planar if and only if it neither contains a subdivision of K5 nor a subdivision of K3,3. Graphs K5 and K3,3 are called the Kuratowski graphs. Applications of Kuratowskis Theorem Any graph can now be either drawn in the

plane or one can find a subdivision of a Kuratowski graph in it. For any graph on n vertices there are efficient algorithms for checking if the graph is planar. The best one runs in linear time ( O(n)). Wagners Theorem Similar to Kuratowski: Theorem (Wagner): Graph G is planar if and only if it contains no subgraph that can

be contracted to one of the two Kuratowski subgraphs. Exercises 12-1 N1. Show that K4 can be embedded in the plane. N2. Show that the Petersen graph can be embedded in the projective plane. N3. Prove: A graph is planar if and only if it can be embedded in a sphere. (Hint: use stereographic projection.)

Exercises 12-2 N4. By using Kuratowskis Theorem show that the Petersen graph is non-planar. N5. By using Wagners Theorem show that the Petersen graph is non-planar. N6. Show that for any planar graph with v vertices, e edges and girth g the following is true: (g-2)e g(v-2) N7. By using Eulers formula show that the Petersen graph is non-planar.

13. Graphs from Polyhedra Skeleta of Geometric Bodies To each geometric polyhedron T we may associate a graph G(T), by selecting the vertices and edges of the polyhedron. The obtained graph is called the skeleton of T. Sometimes we use the same name for the polyhedron and for the graph. Later we will see why such a naming is permitted.

Melancholia I The renowned graphics Melancholia I by Albrecht Drer contains a mysterious body (polyhedron) whose construction is now understood. Drer Polyhedron

It is obtained from an elongated cube by truncating the top and bottom vertex. A polyhedron with 8 faces is obtained: 6 pentagons 2 regular triangles Skeleta of Polyhedra are Modeled by Graphs

On the left we see the Drer graph, with 12 vertices and 18 edges, the skeleton of Drers polyhedron. It is isomorphic to the generalized Petersen graph G(6,2). Steinitz Theorem Theorem [Steinitz]. A simple graph G is planar and 3-connected if and only if it is

the skeleton of a convex three-dimensional polyhedron. Fullerene Fullerene is a convex trivalent polyhedron, whose faces are only pentagons and hexagons. Dodecahedron

The dodecahedron is the smallest fullerene. Buckminster Fullerene The most well-known fullerene is the Buckminster fullerene on 60 vertices. It is a truncated icosahedron. The Buckminster fullerene is a model of

a carbon molecule. Tuttes Planarity Algorithm A cycle C of G is called peripheral if no edge not in C joins two vertices in C G \ C is connected. For example, a face of a 3-connected planar graph can be shown to be a peripheral cycle. The embedding of G in the plane is

barycentric relative to S V(G) if for each vertex u S the point (vector) (u) is the barycenter of the of images of neighbours of u. Tuttes Embedding Theorem [Tutte]. Let C be a peripheral cycle of length d in a connected simple graph G. Let be a mapping from V(C) to the vertices of a convex d-gon in R2 such that adjacent vertices in C are adjacent in

the polygon. The unique barycentric representation relative to C determines a drawing of G in R2. This drawing has no crossings if and only if the graph is planar. [The vertex coordinates in R2 can be obtained by solving a linear system. This gives an O(n3) planarity test algorithm]. Prisms The skeleton of an n-sided prism is denoted by n. It is planar, trivalent and has 2n

vertices. Antiprisms The skeleton of an nsided antiprism is denoted by An. Its graph is planar, tetravalent and has 2n vertices. A6

Mbius Ladders Mbius ladder Mn is obtanied from C2n by adding n main diagonals. M5 Exercises 13-1 N1. The angles in the Drer pentagon (see figure on the

left) indicate fivefold symmetry and thus implicitely the golden section. Determine the lengths of the sides of Drer polyhedron. N2. Determine coordinates of the Drer polyhedron. (Hint: the pentagon on the left has a circumscribed circle.) Exercises 13-2

N3. Prove that each fullerne has exactly 12 pentagonal faces. N4. Prove that each fullerene has an even number of vertices. N5. Prove that a fullerene has at least 20 vertices. N6. Show that for each even n, n 20, n 22 there exists a fullerne on n vertices. Exercises 13-3

N7. Show that n can be obtianed from Mn by deleting and re-attaching two edges. N8. Use Tuttes algorithm to draw the Petersen graph and use one of the pentagonal cycles C5 as the peripheral regular pentagon with unit side length. Verify that the inner cycle is drawn as the pentagram. Determine its side-length. Homework 13 H1. Show that every graph can be embedded in R3

(Hint: place vertices on the helix curve (cos t, sin t, t) or even better on the curve (t,t2,t3). H2. Show that there is only one fullerene on 24 vertices. Draw its skeleton. H3. Prove that none of the Mbius ladders Mn is planar. H4. Use Tuttes algorithm to draw the cube Q3 and use the unit square for the outer face. What is the length of a side in the opposite, inner face? 14. Metric Space - Revisited

Metric Space - Revisited If (M,d) is a metric space, then for any A M with induced metric (A,d) is also a metric space, namely a subspace. A natural question is : when are two metric spaces (M,d) and (M,d) considered isomorphic? There are two types of mappings that are candiates for isomorphism.

Isometries Let (M,d) and (M,d) be two metric spaces. A bijective mapping : M ! M is called isometry, if for every pair of points u,v 2 M we have: d(u,v) = d((u),(v)). Clearly, isometric spaces are indistingushable as far as metric properties are concerned. Euclidean metric in Rn.

The set of real n-tuples R := {x = (x1,x2,...,xn)|xi 2 R, 1 i n} n carries a number of important mathematical structures. The mapping dp(x, y) = [(x1 y1)p + (x2 y2)p + ... + (xn yn)p]1/p. makes (Rn,dp) a metric space for 1 p 1.

For p = 2 the usual Euclidean metric is obtained. Metric in C. Let z = a + bi and w = c + di be two complex numbers. Define d(z,w) := |z w|. Then (C,d) is a metric space. Note that (C,d) is isometric to the Euclidean plane (R,d2).

Similarity I Let (M,d) and (M,d) be two metric spaces. A mapping h:M ! M with the property that for any four points a,b,c,d 2 M we have: If d(a,b) = d(c,d) then d(h(s),h(b)) = d(h(c),h(d)) is called similarity (of type I). Similarity II Let (M,d) and (M,d) be two metric spaces and r 2 R\{0}. A mapping h:M ! M with the property that for any pair of points a,b,

2 M we have: If d(a,b) = r d(h(a),h(b)) then h is called similarity (of type II) and r is called the dilation factor. Type I vs. Type II Clearly each similarity of type II is also a similarity of type I. In general, the converse is false. Theorem. A similarity on (Rn,d2) of type I is also of type II. (Proof can be found in

Paul B. Yale: Geomerty and Symmetry, Dover, 1988 (reprint from 1968)) Finite Metric Space In a finite metric space (M,d) we may assume that min d(u,v) = 1. Max d(u,v) is called the diameter of M. The quotient Max d(u,v)/Min d(u,v) is called dilation coefficient. 15. Representations of Graphs

Representation of Graphs Let G be a graph and let V be a set. A pair of mappings V:V(G) ! V and E:V(G) ! P(V) is called a V-representation of graph G if for any edge e = uv 2 E(G) we have {V(u),V(v)} E(uv). If there is no danger of confusion we will drop the subscripts and denote both mappings simply by . Usually we require V to be a vector space (this is what C. Godsil and G. Royle do in their book Algebraic Graph Theory, Springer, 2001). But that is not always the case. In their definition Godsil and Royle use a single mapping defined on the vertices. In such a

case we may extend the mapping on the edge set in an arbitrary way, for instance by taking E(uv) := {V(u),V(v)}. Representation of Graphs in a Metric Space There are important and deep results by Lszl Lovsz et al. Sometimes we may take V to be a metric space, projective space or some other structure. If (V,d) is a metric space we may define the energy of the representation.

Point Configuration A point configuration S V is a collection of elements of some space V. Later we will consider point configurations in R2 . If is a V-representation of G then the image S = (V(G)) is a point configuration. We say that is vertex faithful

is :V(G) ! S is a bijection. We are mostly interested in vertex faithful representations. Graph Representation An Example For the cube graph Q3 there are several useful representations: [3 dimensional real representation] In R3 the eight vertices are mapped to the eight points of {0,1}3.

The two drawings of Q3 in the Euclidean plane can be interpreted as representations in [2 dimensional real representation] R2 or in [1 dimensional complex representation] C. In the latter case, the points in the complex plane are given by {eik|0

k7}. Extending Representation to Edges Usually we try to extend the mapping to the edges. In the case V = R2 or V= R3 finding a representation means actually drawing graph G in V = R2 or V= R3 . Each edge e=uv is then represented as the line segment connecting (u) and (v). Hence (e) = conv((u),(v)).

In general we extend to the edges : E(G) ! P(V) and require that for e = uv, {(u),(v)} (e). If nothing is said about edge extension, we assume (e) = {(u),(v)}. Edge Extensions (u) (u) (u)

(u) (u) r r (v) (v)

Let e = uv 2 E(G). There are several possible edge extensions: (e) = {(u),(v)}. (e) = {(u),r,(v)}. r = ((u)+(v))/2.

(v) (v) (v)

(e) = conv((u),(v)). (e) = aff((u),(v)) We may speak of barycentric, convex and affine edge extensions, respectively. But there are several other interpretations of Three Classical Results The Steinitz Theorem, Farys Theorem and

Tuttes Theorem can all be interpreted as graph representations. Graph Representation vs. Graph Drawing There is some overlap but there are many differences. In graph drawing (in the broad sense of the word) the object is to find algorithms to draw a graph (usually in the plane) with certain restrictions or with some optimization criterion. [Computer Science Approach.] See for example: Annotated bibliography on graph drawing algorithms, by Di Battista, Eades, Tamassia and Tollis.

In graph representation we label vertices (= add coordinates). We may look at this as a functor from the category of graphs to the category of coordinatized graphs. [Mathematical Approach]. We will use the word graph drawing in a narrow sense of the word. The Energy Usually we try to find among the representations of certain type the one that is optimal in a cetrain sense. To this end we may define an energy function E() and then seek a representation

that minimizes the energy. There are several such energy functions used in various problem areas. Some Energy Models Spring embedders

Molecular mechanics Tutte drawing Schlegel diagram drawing (B. Plestenjak). [Connection to Markov Chains] ... Laplace Representation The Laplace Representation

Let be a representation in Rk. Define E() = uv 2 E(G) ||(u)-(v)||2 An R3 Laplace representation of a fullerene (skeleton of a trivalent polyhedron with pentagonal and hexagonal faces)

It turns out that the minimum (under some reasonable conditions) is achieved as follows. 1. 2. 3. 4. Take the Laplace matrix of G. Q(G) = D(G)-A(G)

Find the eigenvalues 0 = 1 2 ... n. Find the corresponding orthonormal eigenvectors x1, x2, ..., xn. Form a matrix R =[x2|x3| ... |xk+1] Let (vi) = rowi(R). 5. 6. Nodal Domains

A one dimensional representation defines a partition of the vertex set into three classes: V+, V-, V0. A nodal domain is a connected component of the graph induced by V+or V-. [Weak nodal domain V+ [ V0].

Nodal Domains The Example on the left represents nodal domains obtained from the Laplace representation of G(10,4). Congruence and Similarity A representation in any metric sapce, in particular in Rn, can be scaled without

being changed too much. If is injective on the vertices, we may scale it in such a way that Min d(u,v) = 1, for u ~ v. Each vertex faithful representation is similar to a standard one. Unit Distance Graphs Let be a representation in Rk. Define Ep () = (uv 2 E(G) ||(u)-(v)||p) (1/p) We assume that Min uv 2 E(G) ||(u)-(v)|| = 1 In the limit when p ! 1 we get E1 () = Maxuv 2 E(G) ||(u)-(v)||

The number E1 () is called dilation coefficient. Hence E1 () 1. In the special case: E1 () = 1 we call this representation a unit distance graph. Flat Torus r = (rx,ry) s = (sx,sy) Take a unit square and identify two opposite pairs of sides. The

resulting topological space is a torus. In order to make it a metric sapce we can extend the usual Euclidean distance . dT(r,s) := Min{d(r,s+(0,1)), d(r,s+(1,0)), d(r,s+(1,1)), d(r,s+(0,-1)). d(r,s+(-1,0)), d(r,s+ (-1,1)), d(r,s+(1,-1)), d(r,s+(-1,1))}. Embeddings vs. Representations

Let be a nice topological space such as a metric space and G be a general graph. Let a mapping :G be defined having the following properties: 1. :V(G) is injective. 2. For each edge e=uv e:[0,1] is continuous and e( 0) = (u) and e(1) = (v). 3.

In the interior of the interval [0,1] e is injective. Each embedding would qualify. Note that defines a representation of G in . Embeddings are Representations Think of K3 K3 embedded in the torus. The torus, in turn, is embedded in R3. We

obtain a representation of our graph in the torus and another one in R3. Stereographic Projection N T0 T1 There is a homeomorphic

mapping of a sphere without the north pole N to the Euclidean plane R2. It is called a stereographic projection. Take the unit sphere x2 + y2 + z2 = 1 and the plane z = 0. The mapping p:

T0(x0,y0,z0) T1(x1,y1) is shown on the left. Stereographic Projection N T0 T1 The mapping p: T0(x0,y0,z0) T1(x1,y1) is shown

on the left. r1 = r0/(1-z0) x1 = x0/(1-z0) y1 = y0/(1-z0) Stereographic projection and representations We may use stereographic projection to get an R2 drawing from an R3 drawing. Note that the representation of edges is computed anew!

Example Take the Dodecahedron and a random point N on a sphere. The corresponding stereographic projection is depicted below. A better strategy is to take N to be a face center.

Example A better strategy is to take N to be a face center as shown on the left. Only vertices are projected. The edges are re-computed. Schlegel Diagram Schlegel diagram are

defined for (convex) polyhedra. Normally, a Schlegel diagram is definded as a projection of the polyhedron on one of its faces. We understand this notion in a broader sense, namely as a drawing of a graph G within the convex region defined by some of its vertices S

V(G). Exercises 15-1 N1. Given a standard drawing of G(n,r) with inner radius r and outer radius R, determine the dilation coefficient of this planar representation. N2. Select the optimal quotient R/r in the previous exercise. N3. In the unit flat torus draw the circle of radius centered at the point (, ).

Exercises 15-2 N4. Use Laplace representations followed by stereographic projection to get Schlegel diagrams of platonic graphs. N5. Use a generalization of Tuttes method to solve the same problem. N6. Repeat the two exercises for some of the archimedean solids and their duals. N7. Is there a unit distance representation for the subdivision graph S(K4)?

Homework 15 H1. It is easy to verify that K4 is not a unit distance graph in the plane. Consider a drawing of K4 in the plane with only two distinct edge lengths. How many such nonisomorphic drawings are there? (Hint: there are six). Compute the dilation coefficient for all such drawings. 16. Edge-Coloring and Snarks Edge-Coloring of Graphs

On the left we see a 1factorization of 5, the five-sided prism. Each factor is respresented by its own color. No edges of the same color are incident with the same vertex. In other words, each set of monochromatic edges is independent. This idea can be formalized. Edge-Coloring of Graphs

A mapping c:E(G) C from the edge set E(G) to some finite set C is called an (admissible) edge coloring, if for any two edges e and f with a common endvertex c(e) c(f). The least number of colors needed to properly color the edges of G is called chromatic index and is denoted by (G).

Vizings Theorem Theorem: The chromatic index of a simple graph G satisfies the following inequalities: (G) (G) (G)+1 Proof. Lower bound immediate, the upper bound is more difficult to prove. Using Vizings theorem we may now classify simple graphs into two types. A graph of type I has (G) = (G), while the graph of type II has (G) = (G)+1.

Consequences Corollary: A regular graph is of type I, if and only if it has a 1-factorization. Example: The Petersen graph is of type II. Even if we replace a vertex by a triangle in the Petersen graph, the resulting graph remains of type II. Triangle Removal a

c Let G and G be two trivalent graphs that differ only by a triangle. This means that G is obtained from G by replacing any vertex by a triangle as shown on the left. Equivalently, G is obtained from G by a triangle removal. Proposition. If G and G differ by a

triangle then (G) = (G). b Vertex is replaced by triangle. a c b

Snarks Using a similar argument we may prove that cycles of length 4 can be removed in the same sense. A 3-connected trivalent graph of girth > 4 of type II is called

a snark. Families of Snarks There are several infinite families of snarks known. Blanua found the first snark after Petersen. Blanua snarks

Knigs Theorem Theorem (Knig): For a bipartite graph G we have (G) = (G). Exercises 16 N1. Show that there are no bipartite snarks. N2. Repeatedly remove all quadrilaterals and triangles in K3,3. What simple graph is obtained in the end? N3. Dot product!

17. Vertex Colorings and Graph Homomorphisms Vertex Coloring of Graphs. A mapping c:V(G) C from the vertex set to a finite set of colors is called vertex coloring, if for any pair of adjacent vertices u ~ v we have c(u) c(v). The least number of colors of some proper vertex coloring of G is called the chromatic number and is denoted by (G).

Brooks Theorem For any connected graph G the following holds: (G) = (G)+ 1, if G is isomorphic to a complete graph or an odd cycle. (G) (G), otherwise. Four Color Theorem A theorem posed in the 19th century and proved in the 20th century.

Theorem: (G) 4, for any planar graph G. Graph Mappings (Homomorphisms) Let :V(G) ! V(H) be a mapping between the vertices of two graphs. is called a graph mapping or graph homomorphism if for any pair of vertices u,v 2 V(G) the fact u ~ v implies (u) ~ (v). More general maps Weak homomorphism

Sometimes we allow graph maps that do not preserve dimension. : V(G) ! V(H) and u ~ v implies (u) ~ (v) or (u) = (v). Such a is called a weak homomorphism. Retracts Let : G ! G be a graph homorphism. Then is called a retraction if 2 = . (idempotent). (G) = H has the property that |H = id. H is called a retract. In a similar way one can define a weak

retraction and weak retract. Colorings revisited. A vertex coloring c with h colors can be defined as a graph homomorphism c:G ! Kh Exercises 17 N1. Prove that retracts and weak retracts are isometric subgraphs. N2(*). A graph G is called a median graph

if for any triple of vertices u,v, w we have | I(u,v) I(v,w) I(w,u)| = 1. Prove that G is a median graph if and only if it is a retract of some hypercube. Statistic page

Number of slides:226 Number of sections:17 Number of exercises:112 Number of homeworks:18

Recently Viewed Presentations

  • The Medical Office Building Kale Mullikin Mechanical Option

    The Medical Office Building Kale Mullikin Mechanical Option

    Ground Coupled Depth. System Design Options. Cost Analysis. Structural Breadth. Joist Redesign. Girder Redesign. Cost. Conclusion. The Medical Office Building Conclusion/Recommendations. Ground coupled system. Saves $3,945/year. Vertical Well - Payback of 28.9 years. Horizontal Well - Payback of 4.9 years....
  • Warm Up - Mrs. Orlando&#x27;s American History

    Warm Up - Mrs. Orlando's American History

    US, British, & Canadian forces. Largest sea invasion in history!!! Allied Gen. in Command Dwight D. Eisenhower planned it. Code-named… D-Day. Faced horrific task . 10,000+ died when landed but… By end of the day they had the beaches and...
  • cseweb.ucsd.edu

    cseweb.ucsd.edu

    BufDesc Class - Clock Algorithm. Used to keep track of the state of each frame. Buffer is described by 4 attributes : Dirty bit: if true indicates that the page is dirty (i.e. has been updated) and thus must be...
  • He who has money smokes cigars But who

    He who has money smokes cigars But who

    ""He who has money smokes cigars But who has no money smokes paper." A good Cuban cigar closes the door to the vulgarities of the world.". La Cultura Cuba many roots, those including African and Russian aside from Spain creating...
  • Treasure &#x27;Chest&#x27; - A Physiological and Pedagogical Review of ...

    Treasure 'Chest' - A Physiological and Pedagogical Review of ...

    "As the bottom of the vocal fold bulges out, the glottis becomes more rectangular than wedge-shaped (convergent). During vibration, then, glottal closure can be obtained over a greater portion of the vocal fold, and thereby over a greater portion of...
  • ETE BIBLE ELAROENA Designed Designed by by Dr.

    ETE BIBLE ELAROENA Designed Designed by by Dr.

    //// From Dan in the North to Beersheba in the south. In spite of all their efforts, though, Joshua's armies do not completely rid the land OF ALL THE Canaanites as God had instructed. This failure to completely obey God's...
  • ANSI/ASHRAE/IES Standard 90.1-2016: Power and Lighting

    ANSI/ASHRAE/IES Standard 90.1-2016: Power and Lighting

    NSI/ASHRAE/IES Standard 90.1-2013, Figure 3.2-1 The daylight area under rooftop monitors is the combined daylight area under each rooftop monitor without double counting over-lapping areas. The daylight area under each rooftop monitor is the product of the width of the...
  • E-books in Scotland

    E-books in Scotland

    Open Access: Developing a National Information Strategy in Scotland Professor Derek Law Information Resources Directorate University of Strathclyde