Line graphs¶
This module gather everything which is related to line graphs. Right now, this amounts to the following functions :
line_graph() |
Computes the line graph of a given graph |
is_line_graph() |
Check whether a graph is a line graph |
root_graph() |
Computes the root graph corresponding to the given graph |
Author:
- Nathann Cohen (01-2013),
root_graph()
method and module documentation. Written while listening to Nina Simone “I wish I knew how it would feel to be free”. Crazy good song. And “Prendre ta douleur”, too.
Definition¶
Given a graph \(G\), the line graph \(L(G)\) of \(G\) is the graph such that
The definition is extended to directed graphs. In this situation, there is an arc \((e,e')\) in \(L(G)\) if the destination of \(e\) is the origin of \(e'\).
For more information, see the Wikipedia page on line graphs.
Root graph¶
A graph whose line graph is \(LG\) is called the root graph of \(LG\). The root graph of a (connected) graph is unique ([Whitney32], [Harary69]), except when \(LG=K_3\), as both \(L(K_3)\) and \(L(K_{1,3})\) are equal to \(K_3\).
Here is how we can “see” \(G\) by staring (very intently) at \(LG\) :
A graph \(LG\) is the line graph of \(G\) if there exists a collection \((S_v)_{v\in G}\) of subsets of \(V(LG)\) such that :
- Every \(S_v\) is a complete subgraph of \(LG\).
- Every \(v\in LG\) belongs to exactly two sets of the family \((S_v)_{v\in G}\).
- Any two sets of \((S_v)_{v\in G}\) have at most one common elements
- For any edge \((u,v)\in LG\) there exists a set of \((S_v)_{v\in G}\) containing both \(u\) and \(v\).
In this family, each set \(S_v\) represent a vertex of \(G\), and contains “the set of edges incident to \(v\) in \(G\)”. Two elements \(S_v,S_{v'}\) have a nonempty intersection whenever \(vv'\) is an edge of \(G\).
Hence, finding the root graph of \(LG\) is the job of finding this collection of sets.
In particular, what we know for sure is that a maximal clique \(S\) of size \(2\) or \(\geq 4\) in \(LG\) corresponds to a vertex of degree \(|S|\) in \(G\), whose incident edges are the elements of \(S\) itself.
The main problem lies with maximal cliques of size 3, i.e. triangles. Those we have to split into two categories, even and odd triangles :
A triangle \(\{e_1,e_2,e_3\}\subseteq V(LG)\) is said to be an odd triangle if there exists a vertex \(e\in V(G)\) incident to exactly one or all of \(\{e_1,e_2,e_3\}\), and it is said to be even otherwise.
The very good point of this definition is that an inclusionwise maximal clique which is an odd triangle will always correspond to a vertex of degree 3 in \(G\), while an even triangle could result from either a vertex of degree 3 in \(G\) or a triangle in \(G\). And in order to build the root graph we obviously have to decide which.
Beineke proves in [Beineke70] that the collection of sets we are looking for can be easily found. Indeed it turns out that it is the union of :
- The family of all maximal cliques of \(LG\) of size 2 or \(\geq 4\), as well as all odd triangles.
- The family of all pairs of adjacent vertices which appear in exactly one maximal clique which is an even triangle.
There are actually four special cases to which the decomposition above does not apply, i.e. graphs containing an edge which belongs to exactly two even triangles. We deal with those independently.
- The
Complete graph
\(K_3\). - The
Diamond graph
– the line graph of \(K_{1,3}\) plus an edge. - The
Wheel graph
on \(4+1\) vertices – the line graph of theDiamond graph
- The
Octahedron
– the line graph of \(K_4\).
This decomposition turns out to be very easy to implement :-)
Warning
Even though the root graph is NOT UNIQUE for the triangle, this method returns \(K_{1,3}\) (and not \(K_3\)) in this case. Pay very close attention to that, for this answer is not theoretically correct : there is no unique answer in this case, and we deal with it by returning one of the two possible answers.
[Whitney32] | Congruent graphs and the connectivity of graphs, Whitney, American Journal of Mathematics, pages 150–168, 1932, available on JSTOR |
[Harary69] | Graph Theory, Harary, Addison-Wesley, 1969 |
[Beineke70] | Lowell Beineke, Characterizations of derived graphs, Journal of Combinatorial Theory, Vol. 9(2), pages 129-135, 1970 http://dx.doi.org/10.1016/S0021-9800(70)80019-9 |
Functions¶
-
sage.graphs.line_graph.
is_line_graph
(g, certificate=False)¶ Tests wether the graph is a line graph.
INPUT:
certificate
(boolean) – whether to return a certificate along with the boolean result. Here is what happens whencertificate = True
:- If the graph is not a line graph, the method returns a pair
(b, subgraph)
whereb
isFalse
andsubgraph
is a subgraph isomorphic to one of the 9 forbidden induced subgraphs of a line graph. - If the graph is a line graph, the method returns a triple
(b,R,isom)
whereb
isTrue
,R
is a graph whose line graph is the graph given as input, andisom
is a map associating an edge ofR
to each vertex of the graph.
- If the graph is not a line graph, the method returns a pair
Todo
This method sequentially tests each of the forbidden subgraphs in order to know whether the graph is a line graph, which is a very slow method. It could eventually be replaced by
root_graph()
when this method will not require an exponential time to run on general graphs anymore (see its documentation for more information on this problem)... and if it can be improved to return negative certificates !Note
This method wastes a bit of time when the input graph is not connected. If you have performance in mind, it is probably better to only feed it with connected graphs only.
See also
- The
line_graph
module. line_graph_forbidden_subgraphs()
– the forbidden subgraphs of a line graph.line_graph()
EXAMPLES:
A complete graph is always the line graph of a star:
sage: graphs.CompleteGraph(5).is_line_graph() True
The Petersen Graph not being claw-free, it is not a line graph:
sage: graphs.PetersenGraph().is_line_graph() False
This is indeed the subgraph returned:
sage: C = graphs.PetersenGraph().is_line_graph(certificate = True)[1] sage: C.is_isomorphic(graphs.ClawGraph()) True
The house graph is a line graph:
sage: g = graphs.HouseGraph() sage: g.is_line_graph() True
But what is the graph whose line graph is the house ?:
sage: is_line, R, isom = g.is_line_graph(certificate = True) sage: R.sparse6_string() ':DaHI~' sage: R.show() sage: isom {0: (0, 1), 1: (0, 2), 2: (1, 3), 3: (2, 3), 4: (3, 4)}
TESTS:
Disconnected graphs:
sage: g = 2*graphs.CycleGraph(3) sage: gl = g.line_graph().relabel(inplace = False) sage: new_g = gl.is_line_graph(certificate = True)[1] sage: g.line_graph().is_isomorphic(gl) True
-
sage.graphs.line_graph.
line_graph
(self, labels=True)¶ Returns the line graph of the (di)graph.
INPUT:
labels
(boolean) – whether edge labels should be taken in consideration. Iflabels=True
, the vertices of the line graph will be triples(u,v,label)
, and pairs of vertices otherwise.This is set to
True
by default.
The line graph of an undirected graph G is an undirected graph H such that the vertices of H are the edges of G and two vertices e and f of H are adjacent if e and f share a common vertex in G. In other words, an edge in H represents a path of length 2 in G.
The line graph of a directed graph G is a directed graph H such that the vertices of H are the edges of G and two vertices e and f of H are adjacent if e and f share a common vertex in G and the terminal vertex of e is the initial vertex of f. In other words, an edge in H represents a (directed) path of length 2 in G.
Note
As a
Graph
object only accepts hashable objects as vertices (and as the vertices of the line graph are the edges of the graph), this code will fail if edge labels are not hashable. You can also set the argumentlabels=False
to ignore labels.See also
- The
line_graph
module. line_graph_forbidden_subgraphs()
– the forbidden subgraphs of a line graph.is_line_graph()
– tests whether a graph is a line graph.
EXAMPLES:
sage: g = graphs.CompleteGraph(4) sage: h = g.line_graph() sage: h.vertices() [(0, 1, None), (0, 2, None), (0, 3, None), (1, 2, None), (1, 3, None), (2, 3, None)] sage: h.am() [0 1 1 1 1 0] [1 0 1 1 0 1] [1 1 0 0 1 1] [1 1 0 0 1 1] [1 0 1 1 0 1] [0 1 1 1 1 0] sage: h2 = g.line_graph(labels=False) sage: h2.vertices() [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] sage: h2.am() == h.am() True sage: g = DiGraph([[1..4],lambda i,j: i<j]) sage: h = g.line_graph() sage: h.vertices() [(1, 2, None), (1, 3, None), (1, 4, None), (2, 3, None), (2, 4, None), (3, 4, None)] sage: h.edges() [((1, 2, None), (2, 3, None), None), ((1, 2, None), (2, 4, None), None), ((1, 3, None), (3, 4, None), None), ((2, 3, None), (3, 4, None), None)]
Tests:
sage: g = graphs.KneserGraph(7,1) sage: C = graphs.CompleteGraph(7) sage: C.is_isomorphic(g) True sage: C.line_graph().is_isomorphic(g.line_graph()) True
-
sage.graphs.line_graph.
root_graph
(g, verbose=False)¶ Computes the root graph corresponding to the given graph
See the documentation of
sage.graphs.line_graph
to know how it works.INPUT:
g
– a graphverbose
(boolean) – display some information about what is happening inside of the algorithm.
Note
It is best to use this code through
is_line_graph()
, which first checks that the graph is indeed a line graph, and deals with the disconnected case. But if you are sure of yourself, dig in !Warning
- This code assumes that the graph is connected.
- If the graph is not a line graph, this implementation will take a loooooong time to run. Its first step is to enumerate all maximal cliques, and that can take a while for general graphs. As soon as there is a way to iterate over maximal cliques without first building the (long) list of them this implementation can be updated, and will deal reasonably with non-line graphs too !
TESTS:
All connected graphs on 6 vertices:
sage: from sage.graphs.line_graph import root_graph sage: def test(g): ... gl = g.line_graph(labels = False) ... d=root_graph(gl) sage: for i,g in enumerate(graphs(6)): # long time ... if not g.is_connected(): # long time ... continue # long time ... test(g) # long time
Non line-graphs:
sage: root_graph(graphs.PetersenGraph()) Traceback (most recent call last): ... ValueError: This graph is not a line graph !
Small corner-cases:
sage: from sage.graphs.line_graph import root_graph sage: root_graph(graphs.CompleteGraph(3)) (Complete bipartite graph: Graph on 4 vertices, {0: (0, 1), 1: (0, 2), 2: (0, 3)}) sage: root_graph(graphs.OctahedralGraph()) (Complete graph: Graph on 4 vertices, {0: (0, 1), 1: (0, 2), 2: (0, 3), 3: (1, 2), 4: (1, 3), 5: (2, 3)}) sage: root_graph(graphs.DiamondGraph()) (Graph on 4 vertices, {0: (0, 3), 1: (0, 1), 2: (0, 2), 3: (1, 2)}) sage: root_graph(graphs.WheelGraph(5)) (Diamond Graph: Graph on 4 vertices, {0: (1, 2), 1: (0, 1), 2: (0, 2), 3: (2, 3), 4: (1, 3)})