# Graph Theory Definitions for Midterm 1

### Card Set Information

 Author: Jamie_Bee ID: 309452 Filename: Graph Theory Definitions for Midterm 1 Updated: 2015-10-11 20:49:15 Tags: GraphTheory Folders: Description: Graph Theory Definitions for Midterm 1 Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user Jamie_Bee on FreezingBlue Flashcards. What would you like to do?

1. Neighbourhood
The neighbourhood of a vertex v is the set of neighbours of v, and is denoted by NG(v)
2. Underlying simple graph of G
The simple graph obtained by deleting all loops and all but one of each set of multiple edges
3. Graph Complement
• simple graph with vertex set V()=V(G) in which uv∈ E() if and only if uv ∉ E(G).
• The edge set of is the set of nonedges of G.
• =G.
4. Clique
a set of pairwise adjacent vertices.
5. clique number and symbol
• cardinality of a largest clique in G
• ω(G)
6. independent/stable set
7. independence number and symbol
• cardinality of a largest independent set in G
• α(G)
8. chromatic number and symbol
• the minimum number of colours needed to colour the vertices of G so that distinct adjacent vertices receive different colours
• χ(G)
9. k-partite graph
the vertex set of a k-partite graph can be partitioned into k independent sets
10. planar
A graph is planar if it is possible to draw a diagram of it in the plane without crossing.
11. path
a simple graph whose vertices are ordered so that two vertices are adjacent if and only if they're consecutive
12. cycle
a graph whose vertices are ordered in a circle so that two vertices are adjacent if and only if they are consecutive on the circle.
13. subgraph
a subgraph of G is a graph H such that V(H)⊆V(G) and E(H)⊆E(G), and the assignment of endpoints to edges in H is the same as in G
14. degree of a vertex v in a graph G
the number of edges incident with v, with each loop counting as two edges.
15. minimum degree symbol
δ(G)
16. maximum degree symbol
Δ(G)
17. incidence matrix and symbol
• M(G)
• nxm matrix with rows as the vertex set and columns the edge set, in which the ij0th entri is the number of times vi is incident with ej
18. adjacency matrix of G and symbol
• A(G)
• nxn matrix with rows and columns indexed by the vertex set of G, in which the ij-th entry is the number of edges joining vi and vj in G
19. Two graphs G and H are identical (equal) if
V(G)=V(H), E(G)=E(H)
20. Isomorphism
A simple graph G is said to be isomorphic to a simple graph H if there is a bijection f:V(G)→V(H) such that uv∈E(G)⇔ f(u)f(v)∈E(H)
21. Line graph
the simple graph with vertex set V(L(G))=E(G) in which two vertices are joined if and only if they are adjacent edges in G.
22. self complementary graphs
A simple graph G is self complementary if G≃
23. a decomposition of a graph G
• a list of subgraphs of G such that each edge of G lies in exactly one subgraph in the list.
• The edge sets of the subgraphs in the list partition the edges set of G.
24. k-regular
a graph is k-regular if dG(V) = k for all v∈V(G)
25. girth
• length of a shortest cycle measured in number of edges
• If G has no cycles we say G has infinite girth
26. Union of Graphs G1, G2, ..., Gk
the graph with vertex set and the edge set
27. Disjoint union or sum
If the graphs G1,G2,Gk have pairwise-disjoint vertex sets, then the disjoint union or sum is denoted by G1+G2+...+Gk
28. H-Free
A graph G is H-free if G has no induced subgraph isomorphic to H.
29. walk of length k
an ordered list of alternating vertices and edges
30. trail
a walk with no repeated edge
31. path
a walk with no repeated vertex (and no repeated edge)
32. length of a walk, trail, path or cycle
number of edges, including repetitions if any
33. concatenation in a graph G
• Given a (u,v)-path P and a (v,w)-path Q in G, the concatenation PQ is the (uw,)-walk obtained by following P from u to v, then following Q from v to w.
• P-1 denotes the (v,u)-path obtained by traversing P backwards from v to u.
34. cut-edge (cut-vertex)
a edge e (vertex v) such that G-e (G-v) ihas more components than G
35. Eulerian trail
a trail which uses every edge of G exactly once
36. When is a graph Eulerian?
• If it contains a Eulerian circuit, which is a closed Eulerian trail
• Result: A graph G is Eulerian if and only if it has at most one nontrivial component and is even.
37. even (odd) graph
a graph in which all vertices have even (odd) degree.
38. maximal path in a graph G
a path which is not contained in a longer path of G
39. maximum path in G
a path of maximum length.
40. order and symbol
• n(G)
• Order is the cardinality of the vertex set of G
41. size and symbol
• e(G)
• Size is the cardinality of the edge set of G
42. degree sequence
is the list of vertex degrees of a graph, usually written in nonincreasing order.
43. graphic
a degree sequence of nonnegative integers is graphic if there is a simple graph with degree sequence d.
44. acyclic
graph with no cycles
45. forest
acyclic graph
46. tree
connected acyclic graph
47. leaf or pendant vertex
vertex with degree 1
48. spanning tree of graph G
• spanning subgraph H of G that is a tree
• ie, V(G)=V(G)
49. distance from u to v
• if vertices u and v are connected in graph G, then the distance from u to v denoted by dG(u,v) is the length of a shortest (u,v)-path in G.
• If u and v are not connected in G, then dG(u,v) = ∞
50. diameter and symbol
• diam(G)
• maximum distance between any two vertices of G
• Not the length of the longest path but the length of the longest shortest path
51. eccentricity of a vertex u in a graph G and symbol
52. radius of a graph G and symbol
53. center of a graph G
• Subgraph of G induced by the vertices of minimum eccentricity
• ie, the vertices of u such that
54. contracted and symbol
• An edge e of a graph G is said to be contracted if it is deleted and its endpoints are identified.
• G•e
55. optimal tree
minimum-weight spanning tree
56. greedy algorithms
locally optimal heuristics (practical method)

What would you like to do?

Home > Flashcards > Print Preview