# Graph Theory Definitions for Midterm 1

 Neighbourhood The neighbourhood of a vertex v is the set of neighbours of v, and is denoted by NG(v) Underlying simple graph of G The simple graph obtained by deleting all loops and all but one of each set of multiple edges 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. Clique a set of pairwise adjacent vertices. clique number and symbol cardinality of a largest clique in G ω(G) independent/stable set set of pariwise nonadjacent vertices independence number and symbol cardinality of a largest independent set in Gα(G) 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) k-partite graph the vertex set of a k-partite graph can be partitioned into k independent sets planar A graph is planar if it is possible to draw a diagram of it in the plane without crossing. path a simple graph whose vertices are ordered so that two vertices are adjacent if and only if they're consecutive 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. 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 degree of a vertex v in a graph G the number of edges incident with v, with each loop counting as two edges. minimum degree symbol δ(G) maximum degree symbol Δ(G) 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 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 Two graphs G and H are identical (equal) if V(G)=V(H), E(G)=E(H) 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) 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. self complementary graphs A simple graph G is self complementary if G≃ 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. k-regular a graph is k-regular if dG(V) = k for all v∈V(G) girth length of a shortest cycle measured in number of edgesIf G has no cycles we say G has infinite girth Union of Graphs G1, G2, ..., Gk the graph with vertex set and the edge set 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 H-Free A graph G is H-free if G has no induced subgraph isomorphic to H. walk of length k an ordered list of alternating vertices and edges trail a walk with no repeated edge path a walk with no repeated vertex (and no repeated edge) length of a walk, trail, path or cycle number of edges, including repetitions if any 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. cut-edge (cut-vertex) a edge e (vertex v) such that G-e (G-v) ihas more components than G Eulerian trail a trail which uses every edge of G exactly once When is a graph Eulerian? If it contains a Eulerian circuit, which is a closed Eulerian trailResult: A graph G is Eulerian if and only if it has at most one nontrivial component and is even. even (odd) graph a graph in which all vertices have even (odd) degree. maximal path in a graph G a path which is not contained in a longer path of G maximum path in G a path of maximum length. order and symbol n(G)Order is the cardinality of the vertex set of G size and symbol e(G)Size is the cardinality of the edge set of G degree sequence is the list of vertex degrees of a graph, usually written in nonincreasing order. graphic a degree sequence of nonnegative integers is graphic if there is a simple graph with degree sequence d. acyclic graph with no cycles forest acyclic graph tree connected acyclic graph leaf or pendant vertex vertex with degree 1 spanning tree of graph G spanning subgraph H of G that is a treeie, V(G)=V(G) 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) = ∞ diameter and symbol diam(G)maximum distance between any two vertices of GNot the length of the longest path but the length of the longest shortest path eccentricity of a vertex u in a graph G and symbol radius of a graph G and symbol rad(G) center of a graph G Subgraph of G induced by the vertices of minimum eccentricityie, the vertices of u such that 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 optimal tree minimum-weight spanning tree greedy algorithms locally optimal heuristics (practical method) AuthorJamie_Bee ID309452 Card SetGraph Theory Definitions for Midterm 1 DescriptionGraph Theory Definitions for Midterm 1 Updated2015-10-12T00:49:15Z Show Answers