![]() ![]() Since maximum matchings may be found in polynomial time, so may the maximum independent sets of line graphs, despite the hardness of the maximum independent set problem for more general families of graphs. In particular, a maximum independent set in L( G) corresponds to maximum matching in G. An independent set in L( G) corresponds to a matching in G.For a graph G with n vertices and m edges, the number of vertices of the line graph L( G) is m, and the number of edges of L( G) is half the sum of the squares of the degrees of the vertices in G, minus m.A line graph has an articulation point if and only if the underlying graph has a bridge for which neither endpoint has degree one.However, a graph G that has some isolated vertices, and is therefore disconnected, may nevertheless have a connected line graph. If G is connected, it contains a path connecting any two of its edges, which translates into a path in L( G) containing any two of the vertices of L( G). The line graph of a connected graph is connected.For instance, a matching in G is a set of edges no two of which are adjacent, and corresponds to a set of vertices in L( G) no two of which are adjacent, that is, an independent set. Properties of a graph G that depend only on adjacency between edges may be translated into equivalent properties in L( G) that depend on adjacency between vertices. Properties Translated properties of the underlying graph Green vertex 1,3 is adjacent to three other green vertices: 1,4 and 1,2 (corresponding to edges sharing the endpoint 1 in the blue graph) and 4,3 (corresponding to an edge sharing the endpoint 3 in the blue graph). For instance, the green vertex on the right labeled 1,3 corresponds to the edge on the left between the blue vertices 1 and 3. Each vertex of the line graph is shown labeled with the pair of endpoints of the corresponding edge in the original graph. The following figures show a graph (left, with blue vertices) and its line graph (right, with green vertices). That is, it is the intersection graph of the edges of G, representing each edge by the set of its two endpoints. two vertices of L( G) are adjacent if and only if their corresponding edges share a common endpoint ("are incident") in G.each vertex of L( G) represents an edge of G and.Given a graph G, its line graph L( G) is a graph such that Various extensions of the concept of a line graph have been studied, including line graphs of line graphs, line graphs of multigraphs, line graphs of hypergraphs, and line graphs of weighted graphs. Line graphs are characterized by nine forbidden subgraphs and can be recognized in linear time. ![]() Line graphs are claw-free, and the line graphs of bipartite graphs are perfect. Many other properties of line graphs follow by translating the properties of the underlying graph from vertices into edges, and by Whitney's theorem the same translation can also be done in the other direction. Hassler Whitney ( 1932) proved that with one exceptional case the structure of a connected graph G can be recovered completely from its line graph. Other terms used for the line graph include the covering graph, the derivative, the edge-to-vertex dual, the conjugate, the representative graph, and the θ-obrazom, as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph. The name line graph comes from a paper by Harary & Norman (1960) although both Whitney (1932) and Krausz (1943) used the construction before this. L( G) is constructed in the following way: for each edge in G, make a vertex in L( G) for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L( G). In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L( G) that represents the adjacencies between edges of G. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |