326:
361:
345:
311:
1216:
1965:
1356:
830:
731:
1340:
1865:, coincides with the line graph for planar graphs with maximum degree three, but is always planar. It has the same vertices as the line graph, but potentially fewer edges: two vertices of the medial graph are adjacent if and only if the corresponding two edges are consecutive on some face of the planar embedding. The medial graph of the
303:
The following figures show a graph (left, with blue vertices) and its line graph (right, with green vertices). Each vertex of the line graph is shown labeled with the pair of endpoints of the corresponding edge in the original graph. For instance, the green vertex on the right labeled 1,3 corresponds
1932:
is a multigraph. In this case, the characterizations of these graphs can be simplified: the characterization in terms of clique partitions no longer needs to prevent two vertices from belonging to the same to cliques, and the characterization by forbidden graphs has seven forbidden graphs instead of
1346:
In this example, the edges going upward, to the left, and to the right from the central degree-four vertex do not have any cliques in common. Therefore, any partition of the graph's edges into cliques would have to have at least one clique for each of these three edges, and these three cliques would
813:
has eight. In the illustration of the diamond graph shown, rotating the graph by 90 degrees is not a symmetry of the graph, but is a symmetry of its line graph. However, all such exceptional cases have at most four vertices. A strengthened version of the
Whitney isomorphism theorem states that, for
1387:), shown on the top left of the illustration of forbidden subgraphs. Therefore, by Beineke's characterization, this example cannot be a line graph. For graphs with minimum degree at least 5, only the six subgraphs in the left and right columns of the figure are needed in the characterization.
1431:
uses only
Whitney's isomorphism theorem. It is complicated by the need to recognize deletions that cause the remaining graph to become a line graph, but when specialized to the static recognition problem only insertions need to be performed, and the algorithm performs the following steps:
1876:
or simple polyhedra, the medial graph operation can be represented geometrically by the operation of cutting off each vertex of the polyhedron by a plane through the midpoints of all its incident edges. This operation is known variously as the second truncation, degenerate truncation, or
187:
can be recovered completely from its line graph. 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. Line graphs are
304:
to the edge on the left between the blue vertices 1 and 3. 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).
1414:
described an efficient data structure for maintaining a dynamic graph, subject to vertex insertions and deletions, and maintaining a representation of the input as a line graph (when it exists) in time proportional to the number of changed edges at each step.
988:. Like the line graphs of complete graphs, they can be characterized with one exception by their numbers of vertices, numbers of edges, and number of shared neighbors for adjacent and non-adjacent points. The one exceptional case is
1426:
are based on characterizations of line graphs involving odd triangles (triangles in the line graph with the property that there exists another vertex adjacent to an odd number of triangle vertices). However, the algorithm of
2848:, Theorem 8.7, p. 79. Harary credits this characterization of line graphs of complete bipartite graphs to Moon and Hoffman. The case of equal numbers of vertices on both sides had previously been proven by Shrikhande.
581:. 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. Similarly, a
1489:
has four or fewer vertices, it might be the case that the line graph representation is not unique. But in this case, the augmented graph is small enough that a representation of it as a line graph can be found by a
1359:
The nine minimal non-line graphs, from
Beineke's forbidden-subgraph characterization of line graphs. A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.
833:
A line perfect graph. The edges in each biconnected component are colored black if the component is bipartite, blue if the component is a tetrahedron, and red if the component is a book of triangles.
1677:
976:), but need not be bipartite as the example of the claw graph shows. The line graphs of bipartite graphs form one of the key building blocks of perfect graphs, used in the proof of the
1375:. That is, a graph is a line graph if and only if no subset of its vertices induces one of these nine graphs. In the example above, the four topmost vertices induce a claw (that is, a
1299:
belongs to exactly two of the cliques. It is the line graph of a graph (rather than a multigraph) if this set of cliques satisfies the additional condition that no two vertices of
1178:
2187:
faithfully but it does not guarantee that dynamics on these two graphs have a simple relationship. One solution is to construct a weighted line graph, that is, a line graph with
788:, there are some other exceptional small graphs with the property that their line graph has a higher degree of symmetry than the graph itself. For instance, the
814:
connected graphs with more than four vertices, there is a one-to-one correspondence between isomorphisms of the graphs and isomorphisms of their line graphs.
3630:
1936:
However, for multigraphs, there are larger numbers of pairs of non-isomorphic graphs that have the same line graphs. For instance a complete bipartite graph
1440:
by adding vertices one at a time, at each step choosing a vertex to add that is adjacent to at least one previously-added vertex. While adding vertices to
1347:
all intersect in that central vertex, violating the requirement that each vertex appear in exactly two cliques. Thus, the graph shown is not a line graph.
1371:). He showed that there are nine minimal graphs that are not line graphs, such that any graph that is not a line graph has one of these nine graphs as an
1908:, and has an edge between two elements whenever they are either incident or adjacent. The total graph may also be obtained by subdividing each edge of
1796:
For connected graphs that are not paths, all sufficiently high numbers of iteration of the line graph operation produce graphs that are
Hamiltonian.
2903:, Theorem 8.4, p. 74, gives three equivalent characterizations of line graphs: the partition of the edges into cliques, the property of being
4356:
2183:. Put another way, the Whitney graph isomorphism theorem guarantees that the line graph almost always encodes the topology of the original graph
721:
observe that any method for finding vertex clusters in a complex network can be applied to the line graph and used to cluster its edges instead.
325:
687:. However, not all Hamiltonian cycles in line graphs come from Euler cycles in this way; for instance, the line graph of a Hamiltonian graph
973:
709:
In the context of complex network theory, the line graph of a random network preserves many of the properties of the network such as the
211:
Various extensions of the concept of a line graph have been studied, including line graphs of line graphs, line graphs of multigraphs,
3861:
1557:. Thus, the total time for the whole algorithm is proportional to the sum of the numbers of neighbors of all vertices, which (by the
3453:
3233:
3208:
2598:
2567:
2508:
201:
3673:
1841:. However, there exist planar graphs with higher degree whose line graphs are nonplanar. These include, for example, the 5-star
3813:
3405:
559:
2799:
Roussel, F.; Rusu, I.; Thuillier, H. (2009), "The strong perfect graph conjecture: 40 years of attempts, and its resolution",
2677:
4078:
3993:
3115:
2801:
2745:
536:
420:
1956:
with the same number of edges. Nevertheless, analogues to
Whitney's isomorphism theorem can still be derived in this case.
2515:
Clearly, there is a one-to-one correspondence between the matchings of a graph and the independent sets of its line graph.
1578:
3006:
2753:
2749:
2728:
977:
360:
344:
3547:
1287:
is the line graph of some other graph or multigraph if and only if it is possible to find a collection of cliques in
4277:
Zverovich, I. È. (1997), "An analogue of the
Whitney theorem for edge graphs of multigraphs, and edge multigraphs",
3934:
3700:
Hemminger, R. L.; Beineke, L. W. (1978), "Line graphs and line digraphs", in
Beineke, L. W.; Wilson, R. J. (eds.),
2299:
2285:
212:
4022:
Ryjáček, Zdeněk; Vrána, Petr (2011), "Line graphs of multigraphs and
Hamilton-connectedness of claw-free graphs",
4361:
863:
1276:
belongs to exactly two of them (the two cliques corresponding to the two endpoints of the corresponding edge in
1006:. When both sides of the bipartition have the same number of vertices, these graphs are again strongly regular.
653:
is an edge-transitive graph that has at least five vertices, is not bipartite, and has odd vertex degrees, then
1878:
1376:
985:
2593:, London Mathematical Society Student Texts, vol. 54, Cambridge: Cambridge University Press, p. 44,
2134:. If we now perform the same type of random walk on the vertices of the line graph, the frequency with which
1774:
then each subsequent graph in the sequence is a shorter path until eventually the sequence terminates with an
2257:. It is straightforward to extend this definition of a weighted line graph to cases where the original graph
468:
that has some isolated vertices, and is therefore disconnected, may nevertheless have a connected line graph.
4351:
638:
616:
582:
551:
401:
276:
1136:
310:
2526:
The need to consider isolated vertices when considering the connectivity of line graphs is pointed out by
902:
3594:
Greenwell, D. L.; Hemminger, Robert L. (1972), "Forbidden subgraphs for graphs with planar line graphs",
3440:, London Mathematical Society Lecture Note Series, vol. 314, Cambridge: Cambridge University Press,
1549:
Each step either takes constant time, or involves finding a vertex cover of constant size within a graph
1061:(a book of one or more triangles all sharing a common edge). Every line perfect graph is itself perfect.
3712:
2762:
2394:
1823:
1240:
1108:
1037:
882:
634:
608:
521:
476:
243:
4076:
Sysło, Maciej M. (1982), "A labeling algorithm to recognize a line digraph and output its root graph",
3770:
Lehot, Philippe G. H. (1974), "An optimal algorithm to detect a line graph and output its root graph",
1541:) that connects these two vertices. If there is only one vertex in the cover, then add a new vertex to
1533:
consisting of one vertex or two non-adjacent vertices. If there are two vertices in the cover, augment
1402:
described linear time algorithms for recognizing line graphs and reconstructing their original graphs.
3393:
Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J. (eds.),
2727:, Theorem 8.6, p. 79. Harary credits this result to independent papers by L. C. Chang (1959) and
1077:
in the form of a three-leaf tree. As with claw-free graphs more generally, every connected line graph
3892:
3566:
3517:
3157:
1334:
For example, this characterization can be used to show that the following graph is not a line graph:
1033:
1283:
The existence of such a partition into cliques can be used to characterize the line graphs: A graph
746:
are isomorphic, then the underlying graphs are isomorphic, except in the case of the triangle graph
3545:
Evans, T.S.; Lambiotte, R. (2010), "Line Graphs of
Weighted Networks for Overlapping Communities",
2242:(provided neither end is connected to a vertex of degree 1) will have strength 2 in the line graph
1781:
In all remaining cases, the sizes of the graphs in this sequence eventually increase without bound.
1100:
1036:
of odd length greater than three. Equivalently, a graph is line perfect if and only if each of its
756:
714:
710:
439:
72:
3471:
Degiorgi, Daniele Giorgio; Simon, Klaus (1995), "A dynamic algorithm for line graph recognition",
4294:
4211:
4169:
4132:
4047:
3963:
3916:
3882:
3799:
3772:
3737:
3657:
3582:
3556:
3507:
3371:
3181:
2956:
2938:
2828:
2789:
2771:
2707:
2303:
1953:
1491:
1014:
801:
472:
288:
1202:
of a system of vectors: all graphs with this property have been called generalized line graphs.
3496:
Evans, T.S.; Lambiotte, R. (2009), "Line graphs, link partitions and overlapping communities",
1851:
4324:
3908:
3845:
3533:
3498:
3449:
3363:
3250:
3229:
3204:
2594:
2563:
2557:
2504:
2498:
1873:
1855:
1714:
1558:
1215:
699:
684:
30:
This article is about the mathematical concept. For the statistical presentations method, see
3154:
Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985)
2588:
2531:
4286:
4257:
4201:
4193:
4153:
4116:
4087:
4031:
4002:
3953:
3943:
3900:
3857:
3822:
3781:
3721:
3647:
3639:
3603:
3574:
3525:
3476:
3441:
3414:
3355:
3165:
3156:, Ann. New York Acad. Sci., vol. 555, New York: New York Acad. Sci., pp. 310–315,
3124:
3022:
2930:
2810:
2781:
2741:
2689:
2379:
1372:
1123:
1112:
1089:
1074:
1003:
738:(left) and its more-symmetric line graph (right), an exception to the strong Whitney theorem
597:
574:
389:
that depend only on adjacency between edges may be translated into equivalent properties in
57:
4271:
4236:
4165:
4128:
4099:
4068:
4043:
4014:
3836:
3795:
3762:
3733:
3617:
3488:
3463:
3428:
3177:
3138:
2972:
2950:
2824:
2703:
2608:
4267:
4232:
4181:
4161:
4124:
4095:
4064:
4039:
4010:
3832:
3791:
3758:
3729:
3613:
3484:
3459:
3424:
3173:
3134:
2968:
2946:
2904:
2820:
2757:
2699:
2604:
2039:
1969:
1964:
1687:
1355:
1070:
965:
743:
431:
193:
189:
181:
173:
2042:
may be formed by repeating this process of forming directed line graphs, starting from a
981:
3896:
3570:
3521:
3161:
2500:
Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives
408:
is a set of edges no two of which are adjacent, and corresponds to a set of vertices in
17:
3475:, Lecture Notes in Computer Science, vol. 1017, Berlin: Springer, pp. 37–48,
3169:
3110:
3081:
3010:
2989:
2295:
2261:
was directed or even weighted. The principle in all cases is to ensure the line graph
2188:
2043:
1407:
1303:
are both in the same two cliques. Given such a family of cliques, the underlying graph
1199:
1111:, of constructing a graph with a given number of edges and vertices whose largest tree
642:
3749:
Krausz, J. (1943), "Démonstration nouvelle d'un théorème de Whitney sur les réseaux",
3419:
2694:
4345:
4298:
4091:
4006:
3967:
3827:
3741:
3682:
3661:
3608:
3586:
3375:
3129:
3027:
3002:
2908:
2793:
2084:
edges in the line graph. For many types of analysis this means high-degree nodes in
1029:
969:
849:
817:
Analogues of the Whitney isomorphism theorem have been proven for the line graphs of
789:
735:
279:
if and only if their corresponding edges share a common endpoint ("are incident") in
197:
4173:
4136:
3920:
3803:
3185:
2832:
2711:
679:
is connected and has an even number of edges at each vertex, then the line graph of
103:
that have a vertex in common, make an edge between their corresponding vertices in
4051:
3929:
3669:
3625:
3253:
1949:
1862:
1816:
1810:
1530:
940:
867:
646:
130:
used the construction before this. Other terms used for the line graph include the
49:
1327:. By the strong version of Whitney's isomorphism theorem, if the underlying graph
829:
730:
713:(the existence of short paths between all pairs of vertices) and the shape of its
3870:
3578:
1291:(allowing some of the cliques to be single vertices) that partition the edges of
2100:
1913:
1775:
1699:
1339:
1104:
672:
205:
45:
4327:
3904:
3529:
2815:
2785:
1854:
formed by adding two non-crossing diagonals within a regular pentagon, and all
1096:
has an even number of edges, its edges can be partitioned into two-edge paths.
4313:
4206:
3958:
3652:
2480:, Theorem 8.3, p. 72. Harary gives a simplified proof of this theorem by
2356:
have a vertex in common, make an edge between their corresponding vertices in
2291:
1869:
of a plane graph is the same as the medial graph of the original plane graph.
1866:
1789:
is not connected, this classification applies separately to each component of
1771:
1119:
818:
38:
31:
4290:
3480:
3445:
3367:
2574:
925:. The three strongly regular graphs with the same parameters and spectrum as
4332:
4246:Аналог теоремы Уитни для реберных графов мультиграфов и реберные мультиграфы
3258:
944:
3912:
3537:
1331:
has more than four vertices, there can be only one partition of this type.
3786:
3710:
Jung, H. A. (1966), "Zu einem Isomorphiesatz von H. Whitney für Graphen",
3359:
3346:
Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching".
641:. This property can be used to generate families of graphs that (like the
3887:
3862:
10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K
4215:
4157:
4120:
3948:
3725:
3643:
2942:
2562:, Graduate Texts in Mathematics, vol. 173, Springer, p. 112,
1032:. The line perfect graphs are exactly the graphs that do not contain a
767:, which have isomorphic line graphs but are not themselves isomorphic.
4035:
4317:
4061:
Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963)
2776:
1976:
It is also possible to generalize line graphs to directed graphs. If
706:
provides a converse to this for all but one pair of connected graphs.
4223:
Zhang, Fu Ji; Lin, Guo Ning (1987), "On the de Bruijn–Good graphs",
4197:
3152:
McKee, T. A. (1989), "Graph-theoretic model of geographic duality",
2934:
2272:
reflects the dynamics as well as the topology of the original graph
2191:. There are several natural ways to do this. For instance if edges
4262:
3561:
3512:
1467:, then the input is not a line graph and the algorithm terminates.
1323:
with its endpoints being the two cliques containing the vertex in
729:
4063:, Publ. House Czechoslovak Acad. Sci., Prague, pp. 145–150,
2433:
2431:
442:
connecting any two of its edges, which translates into a path in
3681:, Massachusetts: Addison-Wesley, pp. 71–83, archived from
1826:
three, its line graph is planar, and every planar embedding of
4059:
Sedláček, J. (1964), "Some properties of interchange graphs",
3403:
Beineke, L. W. (1970), "Characterizations of derived graphs",
892:. They may also be characterized (again with the exception of
3436:
Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan (2004),
2633:
1129:
of a line graph are at least −2. The reason for this is that
3811:
Maffray, Frédéric (1992), "Kernels in perfect line-graphs",
3628:; Norman, R. Z. (1960), "Some properties of line digraphs",
4184:(1932), "Congruent graphs and the connectivity of graphs",
3473:
Graph-theoretic concepts in computer science (Aachen, 1995)
1463:; if the algorithm ever fails to find an appropriate graph
1311:
is the line graph can be recovered by making one vertex in
1184:
is the signless incidence matrix of the pre-line graph and
400:
that depend on adjacency between vertices. For instance, a
180:) proved that with one exceptional case the structure of a
3848:(1997), "On line graphs of linear 3-uniform hypergraphs",
3080:, Theorem 8.11, p. 81. Harary credits this result to
2612:. Lauri and Scapellato credit this result to Mark Watkins.
295:, representing each edge by the set of its two endpoints.
1553:
whose size is proportional to the number of neighbors of
3113:(1992), "The medial graph and voltage-current duality",
2988:, Theorem 8.5, p. 78. Harary credits the result to
2333:, is constructed in the following way: for each edge in
1904:
has as its vertices the elements (vertices or edges) of
1763:
and all subsequent graphs in the sequence are triangles.
1517:
formed by the edges that correspond to the neighbors of
1254:. The cliques formed in this way partition the edges of
1092:; equivalently, this means that if the underlying graph
3871:"Generating correlated networks from uncorrelated ones"
3041:
2527:
1721:
itself. These are the only connected graphs for which
3869:
Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003),
2961:
Cahiers du Centre d'Études de Recherche Opérationnelle
1690:, only four behaviors are possible for this sequence:
1363:
Another characterization of line graphs was proven in
87:
is constructed in the following way: for each edge in
1581:
1139:
1107:. These graphs have been used to solve a problem in
3932:(1965), "The interchange graph of a finite graph",
2253:corresponding to the two ends that the edge has in
1672:{\displaystyle G,L(G),L(L(G)),L(L(L(G))),\dots .\ }
4107:Trotter, L. E. Jr. (1977), "Line perfect graphs",
3097:
3053:
2921:Sumner, David P. (1974), "Graphs with 1-factors",
1671:
1172:
2923:Proceedings of the American Mathematical Society
2911:-free, and the nine forbidden graphs of Beineke.
2678:"Which graphs are determined by their spectrum?"
2590:Topics in graph automorphisms and reconstruction
2437:
1992:. Two vertices representing directed edges from
1561:) is proportional to the number of input edges.
881:. Triangular graphs are characterized by their
703:
702:then their line graphs are also isomorphic. The
494:edges, the number of vertices of the line graph
4144:de Werra, D. (1978), "On line perfect graphs",
3226:Space Structures—their Harmony and Counterpoint
2715:. See in particular Proposition 8, p. 262.
1713:and each subsequent graph in this sequence are
3333:
3321:
2676:van Dam, Edwin R.; Haemers, Willem H. (2003),
718:
2649:
2634:Ramezanpour, Karimipour & Mashaghi (2003)
1569:
1428:
1411:
691:is itself Hamiltonian, regardless of whether
381:Translated properties of the underlying graph
8:
4318:Information System on Graph Class Inclusions
3631:Rendiconti del Circolo Matematico di Palermo
3297:
3285:
2138:is visited can be completely different from
2030:. That is, each edge in the line digraph of
1928:may naturally be extended to the case where
1505:that equals the line graph of another graph
1419:
1395:
119:
3013:(1986), "Maximum induced trees in graphs",
2587:Lauri, Josef; Scapellato, Raffaele (2003),
2929:(1), American Mathematical Society: 8–12,
2896:
2894:
479:for which neither endpoint has degree one.
475:if and only if the underlying graph has a
419:no two of which are adjacent, that is, an
4261:
4205:
3957:
3947:
3886:
3826:
3785:
3651:
3607:
3560:
3511:
3418:
3128:
3026:
3015:Journal of Combinatorial Theory, Series B
2959:(1975), "A note on matchings in graphs",
2814:
2775:
2693:
2664:
2492:
2490:
2465:
2463:
2034:represents a length-two directed path in
1580:
1151:
1150:
1138:
980:. A special case of these graphs are the
821:, but are more complicated in this case.
800:(two triangles sharing an edge) has four
27:Graph representing edges of another graph
3309:
3093:
2861:
2450:
2448:
2446:
1963:
1354:
1214:
828:
825:Strongly regular and perfect line graphs
664:is a vertex-transitive non-Cayley graph.
200:. Line graphs are characterized by nine
71:that represents the adjacencies between
3704:, Academic Press Inc., pp. 271–305
3438:Spectral generalizations of line graphs
3042:Cvetković, Rowlinson & Simić (2004)
2885:
2873:
2857:
2577:, Chapter 5 ("Colouring"), p. 118.
2528:Cvetković, Rowlinson & Simić (2004)
2469:
2427:
2088:are over-represented in the line graph
1368:
1367:(and reported earlier without proof by
1364:
1002:, which shares its parameters with the
306:
177:
123:
3983:} algorithm for determining the graph
3273:
3077:
3065:
2985:
2900:
2845:
2724:
2660:
2658:
2621:
2543:
2503:, John Wiley & Sons, p. 394,
2477:
2473:
2454:
2103:on the vertices of the original graph
1858:with a vertex of degree four or more.
1219:Partition of a line graph into cliques
1152:
520:is half the sum of the squares of the
453:containing any two of the vertices of
215:, and line graphs of weighted graphs.
127:
4279:Discrete Mathematics and Applications
2408:corresponds to an independent set in
2222:the edge connecting the two vertices
1423:
1403:
1399:
1173:{\displaystyle A=J^{\mathsf {T}}J-2I}
837:The line graph of the complete graph
7:
3975:Roussopoulos, N. D. (1973), "A max {
2645:
2481:
1537:by adding an edge (corresponding to
645:) are vertex-transitive but are not
3064:This result is also Theorem 8.2 of
2682:Linear Algebra and Its Applications
1830:can be extended to an embedding of
1088:with an even number of edges has a
1040:is either bipartite or of the form
3397:, Leipzig: Teubner, pp. 17–33
3203:, University of California Press,
3170:10.1111/j.1749-6632.1989.tb22465.x
2758:"The strong perfect graph theorem"
2172:more frequently in the line graph
2119:is mapped to a unique vertex, say
2107:. This will pass along some edge
1805:Medial graphs and convex polyhedra
25:
2150:was connected to nodes of degree
1924:The concept of the line graph of
1861:An alternative construction, the
1565:Iterating the line graph operator
704:Whitney graph isomorphism theorem
3098:Greenwell & Hemminger (1972)
3054:Metelsky & Tyshkevich (1997)
1988:has one vertex for each edge of
1572:consider the sequence of graphs
1338:
1315:for each clique, and an edge in
1206:Characterization and recognition
1188:is the identity. In particular,
359:
343:
324:
309:
4186:American Journal of Mathematics
3814:Journal of Combinatorial Theory
3702:Selected Topics in Graph Theory
3406:Journal of Combinatorial Theory
2115:. On the other hand, this edge
1948:has the same line graph as the
1235:, the set of edges incident to
4357:Intersection classes of graphs
4079:Information Processing Letters
3994:Information Processing Letters
2497:Paschos, Vangelis Th. (2010),
2438:Hemminger & Beineke (1978)
2012:are connected by an edge from
1654:
1651:
1648:
1642:
1636:
1630:
1621:
1618:
1612:
1606:
1597:
1591:
1:
4275:. Translated into English as
3420:10.1016/S0021-9800(70)80019-9
2695:10.1016/S0024-3795(03)00483-X
2306:of the sets from the family.
2238:. In this way every edge in
1406:generalized these methods to
509:, and the number of edges of
4092:10.1016/0020-0190(82)90080-1
4007:10.1016/0020-0190(73)90029-X
3828:10.1016/0095-8956(92)90028-V
3609:10.1016/0012-365X(72)90058-1
3334:Evans & Lambiotte (2010)
3322:Evans & Lambiotte (2009)
3228:(5th ed.), Birkhäuser,
3201:Polyhedra: A Visual Approach
3130:10.1016/0012-365X(92)90328-D
3028:10.1016/0095-8956(86)90028-6
2099:. For instance, consider a
1065:Other related graph families
978:strong perfect graph theorem
719:Evans & Lambiotte (2009)
438:is connected, it contains a
335:) constructed from edges in
3548:European Physical Journal B
3395:Beiträge zur Graphentheorie
2650:Degiorgi & Simon (1995)
1570:van Rooij & Wilf (1965)
1429:Degiorgi & Simon (1995)
1412:Degiorgi & Simon (1995)
1295:, such that each vertex of
943:, which may be obtained by
726:Whitney isomorphism theorem
4378:
3935:Acta Mathematica Hungarica
3905:10.1103/physreve.67.046107
3672:(1972), "8. Line Graphs",
3579:10.1140/epjb/e2010-00261-8
3530:10.1103/PhysRevE.80.016105
3298:Harary & Norman (1960)
3286:Ryjáček & Vrána (2011)
2816:10.1016/j.disc.2009.05.024
2786:10.4007/annals.2006.164.51
2624:, Theorem 8.8, p. 80.
2556:Diestel, Reinhard (2006),
2546:, Theorem 8.1, p. 72.
2300:line graph of a hypergraph
2286:Line graph of a hypergraph
2283:
2280:Line graphs of hypergraphs
1808:
1545:, adjacent to this vertex.
1436:Construct the input graph
1227:, and an arbitrary vertex
1103:are exactly the claw-free
742:If the line graphs of two
213:line graphs of hypergraphs
120:Harary & Norman (1960)
36:
29:
4244:Зверович, И. Э. (1997),
3224:Loeb, Arthur Lee (1991),
2348:; for every two edges in
2211:, then in the line graph
2203:are incident at a vertex
2020:in the line digraph when
1980:is a directed graph, its
1972:as iterated line digraphs
1916:of the subdivided graph.
1115:is as small as possible.
986:complete bipartite graphs
698:If two simple graphs are
204:and can be recognized in
192:, and the line graphs of
99:; for every two edges in
4291:10.1515/dma.1997.7.3.287
4245:
4146:Mathematical Programming
4109:Mathematical Programming
3481:10.1007/3-540-60618-1_64
3446:10.1017/CBO9780511751752
2065:, each vertex of degree
1377:complete bipartite graph
1009:More generally, a graph
37:Not to be confused with
18:Conjugate (graph theory)
4024:Journal of Graph Theory
3850:Journal of Graph Theory
2161:, it will be traversed
2044:complete directed graph
1223:For an arbitrary graph
903:strongly regular graphs
617:vertex chromatic number
583:rainbow-independent set
560:maximum independent set
4250:Diskretnaya Matematika
3310:Zhang & Lin (1987)
3199:Pugh, Anthony (1976),
2294:may form an arbitrary
2069:in the original graph
1973:
1673:
1360:
1220:
1174:
1038:biconnected components
834:
739:
385:Properties of a graph
257:represents an edge of
118:comes from a paper by
3928:van Rooij, A. C. M.;
3787:10.1145/321850.321853
3713:Mathematische Annalen
3360:10.1007/s004930170006
2763:Annals of Mathematics
1967:
1682:They show that, when
1674:
1497:When adding a vertex
1470:When adding a vertex
1358:
1218:
1175:
1113:induced as a subgraph
1109:extremal graph theory
1049:(the tetrahedron) or
844:is also known as the
832:
733:
635:edge-transitive graph
633:The line graph of an
609:edge chromatic number
238:is a graph such that
3987:from its line graph
3596:Discrete Mathematics
3116:Discrete Mathematics
2802:Discrete Mathematics
2230:can be given weight
2123:, in the line graph
2111:with some frequency
2050:Weighted line graphs
1968:Construction of the
1912:and then taking the
1579:
1137:
1073:, graphs without an
1069:All line graphs are
964:The line graph of a
711:small-world property
471:A line graph has an
430:The line graph of a
148:representative graph
91:, make a vertex in
3897:2003PhRvE..67d6107R
3571:2010EPJB...77..265E
3522:2009PhRvE..80a6105E
3162:1989NYASA.555..310M
2575:free online edition
2337:, make a vertex in
2302:is the same as the
1982:directed line graph
1513:be the subgraph of
1444:, maintain a graph
1420:Roussopoulos (1973)
1396:Roussopoulos (1973)
1351:Forbidden subgraphs
1319:for each vertex in
1099:The line graphs of
804:but its line graph
802:graph automorphisms
715:degree distribution
558:. In particular, a
524:of the vertices in
464:. However, a graph
287:That is, it is the
202:forbidden subgraphs
174:Hassler Whitney
140:edge-to-vertex dual
4325:Weisstein, Eric W.
4207:10338.dmlcz/101067
4158:10.1007/BF01609025
4121:10.1007/BF01593791
3959:10338.dmlcz/140421
3949:10.1007/BF01904834
3846:Tyshkevich, Regina
3773:Journal of the ACM
3726:10.1007/BF01360250
3653:10338.dmlcz/128114
3644:10.1007/BF02854581
3251:Weisstein, Eric W.
2967:(2–3–4): 257–260,
2419:, and vice versa.
2367:. In other words,
2316:disjointness graph
2310:Disjointness graph
2304:intersection graph
1974:
1954:Shannon multigraph
1669:
1501:to a larger graph
1492:brute force search
1418:The algorithms of
1361:
1243:in the line graph
1221:
1170:
1133:can be written as
1015:line perfect graph
835:
740:
619:of its line graph
473:articulation point
289:intersection graph
63:is another graph
4225:Acta Math. Sinica
4036:10.1002/jgt.20498
3499:Physical Review E
2809:(20): 6092–6113,
2742:Chudnovsky, Maria
1874:regular polyhedra
1732:is isomorphic to
1668:
1559:handshaking lemma
1494:in constant time.
1265:. Each vertex of
1239:corresponds to a
984:, line graphs of
695:is also Eulerian.
639:vertex-transitive
596:corresponds to a
550:corresponds to a
434:is connected. If
366:The line graph L(
350:Added edges in L(
227:, its line graph
219:Formal definition
160:interchange graph
154:, as well as the
16:(Redirected from
4369:
4362:Graph operations
4338:
4337:
4301:
4274:
4265:
4239:
4218:
4209:
4176:
4139:
4102:
4071:
4054:
4017:
3970:
3961:
3951:
3942:(3–4): 263–269,
3923:
3890:
3888:cond-mat/0212469
3864:
3844:Metelsky, Yury;
3839:
3830:
3806:
3789:
3765:
3744:
3705:
3695:
3694:
3693:
3687:
3680:
3664:
3655:
3620:
3611:
3589:
3564:
3540:
3515:
3491:
3466:
3431:
3422:
3398:
3380:
3379:
3343:
3337:
3331:
3325:
3319:
3313:
3307:
3301:
3295:
3289:
3283:
3277:
3271:
3265:
3264:
3263:
3246:
3240:
3238:
3221:
3215:
3213:
3196:
3190:
3188:
3149:
3143:
3141:
3132:
3107:
3101:
3091:
3085:
3075:
3069:
3062:
3056:
3051:
3045:
3039:
3033:
3031:
3030:
2999:
2993:
2983:
2977:
2975:
2953:
2918:
2912:
2898:
2889:
2883:
2877:
2871:
2865:
2855:
2849:
2843:
2837:
2835:
2818:
2796:
2779:
2738:
2732:
2722:
2716:
2714:
2697:
2673:
2667:
2665:Zverovich (1997)
2662:
2653:
2643:
2637:
2631:
2625:
2619:
2613:
2611:
2584:
2578:
2572:
2553:
2547:
2541:
2535:
2524:
2518:
2517:
2494:
2485:
2467:
2458:
2452:
2441:
2435:
2418:
2407:
2392:
2380:complement graph
2377:
2366:
2351:
2347:
2336:
2332:
2321:
2275:
2271:
2260:
2256:
2252:
2241:
2237:
2229:
2225:
2221:
2210:
2206:
2202:
2198:
2194:
2186:
2182:
2171:
2160:
2149:
2145:
2137:
2133:
2122:
2118:
2114:
2110:
2106:
2098:
2087:
2083:
2072:
2068:
2064:
2054:In a line graph
2040:de Bruijn graphs
2037:
2033:
2029:
2019:
2015:
2011:
2007:
2003:
1999:
1995:
1991:
1979:
1970:de Bruijn graphs
1947:
1931:
1927:
1911:
1907:
1903:
1899:
1889:The total graph
1856:convex polyhedra
1849:
1840:
1829:
1821:
1792:
1788:
1769:
1762:
1751:
1742:
1735:
1731:
1720:
1712:
1697:
1685:
1678:
1676:
1675:
1670:
1666:
1556:
1552:
1544:
1540:
1536:
1528:
1524:
1520:
1516:
1512:
1508:
1504:
1500:
1488:
1484:
1473:
1466:
1462:
1447:
1443:
1439:
1386:
1373:induced subgraph
1342:
1330:
1326:
1322:
1318:
1314:
1310:
1306:
1302:
1298:
1294:
1290:
1286:
1279:
1275:
1264:
1253:
1238:
1234:
1230:
1226:
1211:Clique partition
1197:
1187:
1183:
1179:
1177:
1176:
1171:
1157:
1156:
1155:
1132:
1128:
1124:adjacency matrix
1095:
1090:perfect matching
1087:
1075:induced subgraph
1071:claw-free graphs
1060:
1048:
1027:
1013:is said to be a
1012:
1004:Shrikhande graph
1001:
960:
938:
924:
905:with parameters
900:
891:
880:
861:
846:triangular graph
843:
812:
799:
787:
778:
766:
754:
744:connected graphs
694:
690:
682:
678:
670:
663:
652:
629:
615:is equal to the
614:
603:
598:rainbow matching
595:
580:
575:maximum matching
572:
557:
549:
531:
527:
519:
508:
504:
493:
489:
485:
467:
463:
452:
437:
418:
407:
399:
388:
363:
347:
328:
313:
294:
291:of the edges of
282:
274:
264:two vertices of
260:
256:
237:
226:
194:bipartite graphs
186:
110:
102:
98:
90:
86:
78:
70:
62:
58:undirected graph
21:
4377:
4376:
4372:
4371:
4370:
4368:
4367:
4366:
4342:
4341:
4323:
4322:
4310:
4305:
4276:
4247:
4243:
4222:
4198:10.2307/2371086
4180:
4143:
4106:
4075:
4058:
4021:
3974:
3927:
3868:
3843:
3810:
3769:
3751:Mat. Fiz. Lapok
3748:
3709:
3699:
3691:
3689:
3685:
3678:
3668:
3624:
3593:
3544:
3495:
3470:
3456:
3435:
3402:
3392:
3388:
3383:
3345:
3344:
3340:
3332:
3328:
3320:
3316:
3308:
3304:
3296:
3292:
3284:
3280:
3272:
3268:
3254:"Rectification"
3249:
3248:
3247:
3243:
3236:
3223:
3222:
3218:
3211:
3198:
3197:
3193:
3151:
3150:
3146:
3111:Archdeacon, Dan
3109:
3108:
3104:
3094:Sedláček (1964)
3092:
3088:
3076:
3072:
3063:
3059:
3052:
3048:
3040:
3036:
3001:
3000:
2996:
2984:
2980:
2957:Las Vergnas, M.
2955:
2935:10.2307/2039666
2920:
2919:
2915:
2899:
2892:
2884:
2880:
2872:
2868:
2862:de Werra (1978)
2856:
2852:
2844:
2840:
2798:
2746:Robertson, Neil
2740:
2739:
2735:
2723:
2719:
2675:
2674:
2670:
2663:
2656:
2644:
2640:
2632:
2628:
2620:
2616:
2601:
2586:
2585:
2581:
2570:
2555:
2554:
2550:
2542:
2538:
2525:
2521:
2511:
2496:
2495:
2488:
2468:
2461:
2453:
2444:
2436:
2429:
2425:
2409:
2398:
2383:
2368:
2357:
2349:
2338:
2334:
2323:
2319:
2312:
2290:The edges of a
2288:
2282:
2273:
2262:
2258:
2254:
2243:
2239:
2231:
2227:
2223:
2212:
2208:
2204:
2200:
2196:
2192:
2184:
2173:
2162:
2151:
2147:
2143:
2142:. If our edge
2135:
2124:
2120:
2116:
2112:
2108:
2104:
2089:
2085:
2074:
2070:
2066:
2055:
2052:
2035:
2031:
2021:
2017:
2013:
2009:
2005:
2001:
1997:
1993:
1989:
1977:
1962:
1946:
1937:
1929:
1925:
1922:
1909:
1905:
1901:
1890:
1887:
1848:
1842:
1831:
1827:
1819:
1813:
1807:
1802:
1800:Generalizations
1790:
1786:
1767:
1753:
1750:
1744:
1740:
1733:
1722:
1718:
1703:
1695:
1688:connected graph
1683:
1577:
1576:
1567:
1554:
1550:
1542:
1538:
1534:
1526:
1522:
1518:
1514:
1510:
1506:
1502:
1498:
1486:
1475:
1471:
1464:
1449:
1445:
1441:
1437:
1408:directed graphs
1393:
1385:
1379:
1353:
1328:
1324:
1320:
1316:
1312:
1308:
1304:
1300:
1296:
1292:
1288:
1284:
1277:
1266:
1255:
1244:
1236:
1232:
1228:
1224:
1213:
1208:
1189:
1185:
1181:
1146:
1135:
1134:
1130:
1126:
1093:
1078:
1067:
1059:
1050:
1047:
1041:
1018:
1010:
999:
989:
974:Kőnig's theorem
966:bipartite graph
958:
948:
945:graph switching
936:
926:
906:
899:
893:
886:
879:
870:
852:
842:
838:
827:
811:
805:
798:
792:
786:
780:
777:
771:
765:
759:
753:
747:
728:
692:
688:
680:
676:
668:
654:
650:
620:
612:
601:
586:
578:
573:corresponds to
563:
555:
540:
537:independent set
529:
525:
510:
506:
495:
491:
487:
483:
465:
454:
443:
435:
432:connected graph
421:independent set
409:
405:
390:
386:
383:
378:
371:
364:
355:
348:
339:
329:
320:
314:
301:
292:
280:
265:
258:
247:
228:
224:
221:
184:
182:connected graph
104:
100:
92:
88:
80:
76:
64:
60:
42:
35:
28:
23:
22:
15:
12:
11:
5:
4375:
4373:
4365:
4364:
4359:
4354:
4352:Graph families
4344:
4343:
4340:
4339:
4320:
4309:
4308:External links
4306:
4304:
4303:
4285:(3): 287–294,
4252:(in Russian),
4241:
4231:(2): 195–205,
4220:
4192:(1): 150–168,
4178:
4152:(2): 236–238,
4141:
4115:(2): 255–259,
4104:
4073:
4056:
4030:(2): 152–173,
4019:
4001:(4): 108–112,
3972:
3925:
3866:
3856:(4): 243–251,
3841:
3808:
3780:(4): 569–575,
3767:
3746:
3720:(3): 270–271,
3707:
3697:
3666:
3638:(2): 161–169,
3622:
3591:
3555:(2): 265–272,
3542:
3493:
3468:
3454:
3433:
3413:(2): 129–135,
3400:
3389:
3387:
3384:
3382:
3381:
3338:
3326:
3314:
3302:
3290:
3278:
3266:
3241:
3234:
3216:
3209:
3191:
3144:
3123:(2): 111–141,
3102:
3086:
3082:Gary Chartrand
3070:
3057:
3046:
3034:
2994:
2990:Gary Chartrand
2978:
2913:
2890:
2886:Trotter (1977)
2878:
2874:Maffray (1992)
2866:
2858:Trotter (1977)
2850:
2838:
2733:
2717:
2668:
2654:
2638:
2626:
2614:
2599:
2579:
2568:
2548:
2536:
2519:
2509:
2486:
2470:Whitney (1932)
2459:
2442:
2440:, p. 273.
2426:
2424:
2421:
2311:
2308:
2296:family of sets
2284:Main article:
2281:
2278:
2189:weighted edges
2051:
2048:
1961:
1958:
1941:
1921:
1918:
1886:
1883:
1846:
1809:Main article:
1806:
1803:
1801:
1798:
1783:
1782:
1779:
1764:
1748:
1737:
1680:
1679:
1665:
1662:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1596:
1593:
1590:
1587:
1584:
1566:
1563:
1547:
1546:
1495:
1468:
1392:
1389:
1383:
1369:Beineke (1968)
1365:Beineke (1970)
1352:
1349:
1344:
1343:
1212:
1209:
1207:
1204:
1200:Gramian matrix
1169:
1166:
1163:
1160:
1154:
1149:
1145:
1142:
1066:
1063:
1054:
1045:
997:
956:
934:
897:
874:
840:
826:
823:
809:
796:
784:
775:
763:
751:
727:
724:
723:
722:
707:
696:
675:, that is, if
665:
643:Petersen graph
631:
605:
533:
480:
469:
382:
379:
377:
374:
373:
372:
365:
358:
356:
349:
342:
340:
331:Vertices in L(
330:
323:
321:
315:
308:
300:
297:
285:
284:
262:
223:Given a graph
220:
217:
132:covering graph
124:Whitney (1932)
122:although both
48:discipline of
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
4374:
4363:
4360:
4358:
4355:
4353:
4350:
4349:
4347:
4335:
4334:
4329:
4326:
4321:
4319:
4315:
4312:
4311:
4307:
4300:
4296:
4292:
4288:
4284:
4280:
4273:
4269:
4264:
4263:10.4213/dm478
4259:
4256:(2): 98–105,
4255:
4251:
4242:
4238:
4234:
4230:
4226:
4221:
4217:
4213:
4208:
4203:
4199:
4195:
4191:
4187:
4183:
4179:
4175:
4171:
4167:
4163:
4159:
4155:
4151:
4147:
4142:
4138:
4134:
4130:
4126:
4122:
4118:
4114:
4110:
4105:
4101:
4097:
4093:
4089:
4085:
4081:
4080:
4074:
4070:
4066:
4062:
4057:
4053:
4049:
4045:
4041:
4037:
4033:
4029:
4025:
4020:
4016:
4012:
4008:
4004:
4000:
3996:
3995:
3990:
3986:
3982:
3978:
3973:
3969:
3965:
3960:
3955:
3950:
3945:
3941:
3937:
3936:
3931:
3926:
3922:
3918:
3914:
3910:
3906:
3902:
3898:
3894:
3889:
3884:
3881:(4): 046107,
3880:
3876:
3872:
3867:
3863:
3859:
3855:
3851:
3847:
3842:
3838:
3834:
3829:
3824:
3820:
3816:
3815:
3809:
3805:
3801:
3797:
3793:
3788:
3783:
3779:
3775:
3774:
3768:
3764:
3760:
3756:
3752:
3747:
3743:
3739:
3735:
3731:
3727:
3723:
3719:
3716:(in German),
3715:
3714:
3708:
3703:
3698:
3688:on 2017-02-07
3684:
3677:
3676:
3671:
3667:
3663:
3659:
3654:
3649:
3645:
3641:
3637:
3633:
3632:
3627:
3623:
3619:
3615:
3610:
3605:
3601:
3597:
3592:
3588:
3584:
3580:
3576:
3572:
3568:
3563:
3558:
3554:
3550:
3549:
3543:
3539:
3535:
3531:
3527:
3523:
3519:
3514:
3509:
3506:(1): 016105,
3505:
3501:
3500:
3494:
3490:
3486:
3482:
3478:
3474:
3469:
3465:
3461:
3457:
3455:0-521-83663-8
3451:
3447:
3443:
3439:
3434:
3430:
3426:
3421:
3416:
3412:
3408:
3407:
3401:
3396:
3391:
3390:
3385:
3377:
3373:
3369:
3365:
3361:
3357:
3353:
3349:
3348:Combinatorica
3342:
3339:
3335:
3330:
3327:
3323:
3318:
3315:
3311:
3306:
3303:
3299:
3294:
3291:
3287:
3282:
3279:
3276:, p. 82.
3275:
3274:Harary (1972)
3270:
3267:
3261:
3260:
3255:
3252:
3245:
3242:
3237:
3235:9783764335885
3231:
3227:
3220:
3217:
3212:
3210:9780520030565
3206:
3202:
3195:
3192:
3187:
3183:
3179:
3175:
3171:
3167:
3163:
3159:
3155:
3148:
3145:
3140:
3136:
3131:
3126:
3122:
3118:
3117:
3112:
3106:
3103:
3099:
3095:
3090:
3087:
3083:
3079:
3078:Harary (1972)
3074:
3071:
3067:
3066:Harary (1972)
3061:
3058:
3055:
3050:
3047:
3043:
3038:
3035:
3029:
3024:
3020:
3016:
3012:
3008:
3007:Saks, Michael
3004:
2998:
2995:
2991:
2987:
2986:Harary (1972)
2982:
2979:
2974:
2970:
2966:
2962:
2958:
2952:
2948:
2944:
2940:
2936:
2932:
2928:
2924:
2917:
2914:
2910:
2906:
2902:
2901:Harary (1972)
2897:
2895:
2891:
2887:
2882:
2879:
2875:
2870:
2867:
2863:
2859:
2854:
2851:
2847:
2846:Harary (1972)
2842:
2839:
2834:
2830:
2826:
2822:
2817:
2812:
2808:
2804:
2803:
2795:
2791:
2787:
2783:
2778:
2773:
2770:(1): 51–229,
2769:
2765:
2764:
2759:
2755:
2754:Thomas, Robin
2751:
2750:Seymour, Paul
2747:
2743:
2737:
2734:
2730:
2729:A. J. Hoffman
2726:
2725:Harary (1972)
2721:
2718:
2713:
2709:
2705:
2701:
2696:
2691:
2687:
2683:
2679:
2672:
2669:
2666:
2661:
2659:
2655:
2651:
2647:
2642:
2639:
2635:
2630:
2627:
2623:
2622:Harary (1972)
2618:
2615:
2610:
2606:
2602:
2600:0-521-82151-7
2596:
2592:
2591:
2583:
2580:
2576:
2571:
2569:9783540261834
2565:
2561:
2560:
2552:
2549:
2545:
2544:Harary (1972)
2540:
2537:
2533:
2529:
2523:
2520:
2516:
2512:
2510:9780470393673
2506:
2502:
2501:
2493:
2491:
2487:
2483:
2479:
2478:Harary (1972)
2475:
2474:Krausz (1943)
2471:
2466:
2464:
2460:
2456:
2455:Harary (1972)
2451:
2449:
2447:
2443:
2439:
2434:
2432:
2428:
2422:
2420:
2416:
2412:
2405:
2401:
2396:
2390:
2386:
2381:
2375:
2371:
2364:
2360:
2355:
2345:
2341:
2330:
2326:
2317:
2309:
2307:
2305:
2301:
2297:
2293:
2287:
2279:
2277:
2269:
2265:
2250:
2246:
2235:
2219:
2215:
2199:in the graph
2190:
2180:
2176:
2169:
2165:
2158:
2154:
2141:
2131:
2127:
2102:
2096:
2092:
2081:
2077:
2062:
2058:
2049:
2047:
2045:
2041:
2028:
2024:
1987:
1983:
1971:
1966:
1960:Line digraphs
1959:
1957:
1955:
1951:
1945:
1940:
1934:
1919:
1917:
1915:
1897:
1893:
1884:
1882:
1880:
1879:rectification
1875:
1870:
1868:
1864:
1859:
1857:
1853:
1845:
1838:
1834:
1825:
1824:vertex degree
1818:
1812:
1804:
1799:
1797:
1794:
1780:
1777:
1773:
1765:
1760:
1756:
1747:
1738:
1729:
1725:
1716:
1710:
1706:
1701:
1693:
1692:
1691:
1689:
1663:
1660:
1657:
1645:
1639:
1633:
1627:
1624:
1615:
1609:
1603:
1600:
1594:
1588:
1585:
1582:
1575:
1574:
1573:
1571:
1564:
1562:
1560:
1532:
1525:. Check that
1496:
1493:
1482:
1478:
1469:
1460:
1456:
1452:
1435:
1434:
1433:
1430:
1425:
1421:
1416:
1413:
1409:
1405:
1401:
1397:
1390:
1388:
1382:
1378:
1374:
1370:
1366:
1357:
1350:
1348:
1341:
1337:
1336:
1335:
1332:
1281:
1273:
1269:
1262:
1258:
1251:
1247:
1242:
1217:
1210:
1205:
1203:
1201:
1196:
1192:
1167:
1164:
1161:
1158:
1147:
1143:
1140:
1125:
1121:
1116:
1114:
1110:
1106:
1102:
1097:
1091:
1085:
1081:
1076:
1072:
1064:
1062:
1058:
1053:
1044:
1039:
1035:
1031:
1030:perfect graph
1025:
1021:
1016:
1007:
1005:
996:
992:
987:
983:
982:rook's graphs
979:
975:
971:
967:
962:
955:
951:
946:
942:
933:
929:
922:
918:
914:
910:
904:
896:
889:
885:, except for
884:
877:
873:
869:
865:
859:
855:
851:
850:Johnson graph
847:
831:
824:
822:
820:
815:
808:
803:
795:
791:
790:diamond graph
783:
774:
768:
762:
758:
750:
745:
737:
736:diamond graph
732:
725:
720:
716:
712:
708:
705:
701:
697:
686:
674:
666:
661:
657:
648:
647:Cayley graphs
644:
640:
636:
632:
627:
623:
618:
610:
606:
599:
593:
589:
584:
576:
570:
566:
561:
553:
547:
543:
538:
534:
523:
517:
513:
502:
498:
490:vertices and
481:
478:
474:
470:
461:
457:
450:
446:
441:
433:
429:
428:
427:
424:
422:
416:
412:
403:
397:
393:
380:
375:
369:
362:
357:
353:
346:
341:
338:
334:
327:
322:
319:
312:
307:
305:
298:
296:
290:
278:
272:
268:
263:
254:
250:
245:
241:
240:
239:
235:
231:
218:
216:
214:
209:
207:
203:
199:
195:
191:
183:
179:
175:
171:
169:
168:derived graph
165:
164:adjoint graph
161:
157:
153:
149:
145:
141:
137:
133:
129:
128:Krausz (1943)
125:
121:
117:
112:
108:
96:
84:
74:
68:
59:
55:
51:
47:
40:
33:
19:
4331:
4328:"Line Graph"
4282:
4278:
4253:
4249:
4228:
4224:
4189:
4185:
4149:
4145:
4112:
4108:
4086:(1): 28–30,
4083:
4077:
4060:
4027:
4023:
3998:
3992:
3988:
3984:
3980:
3976:
3939:
3933:
3878:
3875:Phys. Rev. E
3874:
3853:
3849:
3818:
3817:, Series B,
3812:
3777:
3771:
3754:
3750:
3717:
3711:
3701:
3690:, retrieved
3683:the original
3675:Graph Theory
3674:
3635:
3629:
3599:
3595:
3552:
3546:
3503:
3497:
3472:
3437:
3410:
3404:
3394:
3354:(1): 89–94.
3351:
3347:
3341:
3329:
3317:
3305:
3293:
3281:
3269:
3257:
3244:
3225:
3219:
3200:
3194:
3153:
3147:
3120:
3114:
3105:
3089:
3073:
3060:
3049:
3037:
3021:(1): 61–79,
3018:
3014:
3011:Sós, Vera T.
2997:
2981:
2964:
2960:
2926:
2922:
2916:
2881:
2869:
2853:
2841:
2806:
2800:
2777:math/0212070
2767:
2761:
2736:
2720:
2685:
2681:
2671:
2641:
2629:
2617:
2589:
2582:
2559:Graph Theory
2558:
2551:
2539:
2522:
2514:
2499:
2414:
2410:
2403:
2399:
2388:
2384:
2373:
2369:
2362:
2358:
2353:
2343:
2339:
2328:
2324:
2315:
2313:
2289:
2267:
2263:
2248:
2244:
2233:
2217:
2213:
2207:with degree
2178:
2174:
2167:
2163:
2156:
2152:
2139:
2129:
2125:
2094:
2090:
2079:
2075:
2060:
2056:
2053:
2026:
2022:
1986:line digraph
1985:
1981:
1975:
1950:dipole graph
1943:
1938:
1935:
1923:
1895:
1891:
1888:
1885:Total graphs
1871:
1863:medial graph
1860:
1843:
1836:
1832:
1822:has maximum
1817:planar graph
1814:
1811:Medial graph
1795:
1784:
1758:
1754:
1745:
1727:
1723:
1708:
1704:
1686:is a finite
1681:
1568:
1548:
1531:vertex cover
1480:
1476:
1458:
1454:
1450:
1424:Lehot (1974)
1417:
1404:Sysło (1982)
1400:Lehot (1974)
1394:
1380:
1362:
1345:
1333:
1282:
1271:
1267:
1260:
1256:
1249:
1245:
1222:
1194:
1190:
1117:
1105:block graphs
1098:
1083:
1079:
1068:
1056:
1051:
1042:
1034:simple cycle
1023:
1019:
1008:
994:
990:
963:
953:
949:
941:Chang graphs
931:
927:
920:
916:
912:
908:
894:
887:
875:
871:
868:Kneser graph
857:
853:
845:
836:
816:
806:
793:
781:
772:
769:
760:
748:
741:
659:
655:
625:
621:
591:
587:
568:
564:
545:
541:
515:
511:
500:
496:
482:For a graph
459:
455:
448:
444:
425:
414:
410:
395:
391:
384:
367:
351:
336:
332:
317:
302:
286:
270:
266:
252:
248:
233:
229:
222:
210:
172:
167:
163:
159:
155:
151:
147:
143:
139:
135:
131:
115:
113:
106:
94:
82:
66:
53:
50:graph theory
46:mathematical
43:
4314:Line graphs
4182:Whitney, H.
3930:Wilf, H. S.
3003:Erdős, Paul
2797:. See also
2688:: 241–272,
2646:Jung (1966)
2482:Jung (1966)
2101:random walk
1920:Multigraphs
1900:of a graph
1776:empty graph
1700:cycle graph
1474:to a graph
1120:eigenvalues
819:multigraphs
770:As well as
685:Hamiltonian
673:Euler cycle
667:If a graph
611:of a graph
206:linear time
4346:Categories
3821:(1): 1–8,
3692:2013-11-08
3670:Harary, F.
3626:Harary, F.
3386:References
2573:. Also in
2532:p. 32
2322:, denoted
2292:hypergraph
1867:dual graph
1772:path graph
1743:is a claw
1715:isomorphic
1485:for which
1448:for which
1391:Algorithms
1307:for which
915:– 1)/2, 2(
864:complement
700:isomorphic
376:Properties
166:, and the
156:edge graph
150:, and the
136:derivative
116:line graph
54:line graph
39:path graph
32:line chart
4333:MathWorld
4299:120525090
3968:122866512
3757:: 75–85,
3742:119898359
3662:122473974
3602:: 31–34,
3587:119504507
3562:0912.4389
3513:0903.2181
3376:207006642
3368:1439-6912
3259:MathWorld
2905:claw-free
2794:119151552
2298:, so the
2000:and from
1852:gem graph
1661:…
1162:−
901:) as the
862:, or the
190:claw-free
152:θ-obrazom
144:conjugate
114:The name
4174:37062237
4137:38906333
3921:33054818
3913:12786436
3804:15036484
3538:19658772
3186:86300941
2907:and odd
2833:16049392
2756:(2006),
2712:32070167
2457:, p. 71.
2352:that do
2073:creates
1180:, where
939:are the
755:and the
552:matching
528:, minus
402:matching
277:adjacent
4272:1468075
4237:0891925
4216:2371086
4166:0509968
4129:0457293
4100:0678028
4069:0173255
4052:8880045
4044:2778727
4015:0424435
3893:Bibcode
3837:1159851
3796:0347690
3763:0018403
3734:0197353
3618:0297604
3567:Bibcode
3518:Bibcode
3489:1400011
3464:2120511
3429:0262097
3178:1018637
3158:Bibcode
3139:1172842
2973:0412042
2951:0323648
2943:2039666
2909:diamond
2825:2552645
2731:(1960).
2704:2022290
2609:1971819
2378:is the
2038:. The
1815:When a
1752:, then
1198:is the
1122:of the
970:perfect
923:– 2, 4)
883:spectra
866:of the
671:has an
522:degrees
299:Example
198:perfect
176: (
44:In the
4297:
4270:
4235:
4214:
4172:
4164:
4135:
4127:
4098:
4067:
4050:
4042:
4013:
3966:
3919:
3911:
3835:
3802:
3794:
3761:
3740:
3732:
3660:
3616:
3585:
3536:
3487:
3462:
3452:
3427:
3374:
3366:
3232:
3207:
3184:
3176:
3137:
2971:
2949:
2941:
2831:
2823:
2792:
2710:
2702:
2607:
2597:
2566:
2507:
2395:clique
2082:− 1)/2
1933:nine.
1914:square
1850:, the
1667:
1529:has a
1509:, let
1241:clique
919:– 2),
848:, the
477:bridge
426:Thus,
316:Graph
244:vertex
162:, the
158:, the
146:, the
142:, the
138:, the
134:, the
56:of an
52:, the
4295:S2CID
4212:JSTOR
4170:S2CID
4133:S2CID
4048:S2CID
3964:S2CID
3917:S2CID
3883:arXiv
3800:S2CID
3738:S2CID
3686:(PDF)
3679:(PDF)
3658:S2CID
3583:S2CID
3557:arXiv
3508:arXiv
3372:S2CID
3182:S2CID
2939:JSTOR
2829:S2CID
2790:S2CID
2772:arXiv
2708:S2CID
2423:Notes
1770:is a
1702:then
1698:is a
1101:trees
1028:is a
972:(see
947:from
810:1,2,2
797:1,1,2
649:: if
486:with
261:; and
242:each
73:edges
3909:PMID
3534:PMID
3450:ISBN
3364:ISSN
3230:ISBN
3205:ISBN
2595:ISBN
2564:ISBN
2505:ISBN
2393:. A
2314:The
2236:− 1)
2226:and
2195:and
1952:and
1872:For
1422:and
1398:and
1118:All
1055:1,1,
907:srg(
860:, 2)
779:and
757:claw
734:The
607:The
440:path
275:are
196:are
178:1932
126:and
4287:doi
4258:doi
4202:hdl
4194:doi
4154:doi
4117:doi
4088:doi
4032:doi
4003:doi
3991:",
3954:hdl
3944:doi
3901:doi
3858:doi
3823:doi
3782:doi
3722:doi
3718:164
3648:hdl
3640:doi
3604:doi
3575:doi
3526:doi
3477:doi
3442:doi
3415:doi
3356:doi
3166:doi
3125:doi
3121:104
3023:doi
2931:doi
2811:doi
2807:309
2782:doi
2768:164
2690:doi
2686:373
2397:in
2382:of
2354:not
2318:of
2232:1/(
2146:in
2016:to
2008:in
2004:to
1996:to
1984:or
1847:1,5
1785:If
1766:If
1749:1,3
1739:If
1717:to
1694:If
1521:in
1384:1,3
1280:).
1231:in
1193:+ 2
1017:if
998:4,4
968:is
890:= 8
785:1,3
764:1,3
683:is
637:is
600:in
585:in
577:in
562:in
554:in
539:in
535:An
505:is
404:in
246:of
79:.
75:of
4348::
4330:.
4316:,
4293:,
4281:,
4268:MR
4266:,
4248:,
4233:MR
4229:30
4227:,
4210:,
4200:,
4190:54
4188:,
4168:,
4162:MR
4160:,
4150:15
4148:,
4131:,
4125:MR
4123:,
4113:12
4111:,
4096:MR
4094:,
4084:15
4082:,
4065:MR
4046:,
4040:MR
4038:,
4028:66
4026:,
4011:MR
4009:,
3997:,
3962:,
3952:,
3940:16
3938:,
3915:,
3907:,
3899:,
3891:,
3879:67
3877:,
3873:,
3854:25
3852:,
3833:MR
3831:,
3819:55
3798:,
3792:MR
3790:,
3778:21
3776:,
3759:MR
3755:50
3753:,
3736:,
3730:MR
3728:,
3656:,
3646:,
3634:,
3614:MR
3612:,
3598:,
3581:,
3573:,
3565:,
3553:77
3551:,
3532:,
3524:,
3516:,
3504:80
3502:,
3485:MR
3483:,
3460:MR
3458:,
3448:,
3425:MR
3423:,
3409:,
3370:.
3362:.
3352:21
3350:.
3256:.
3180:,
3174:MR
3172:,
3164:,
3135:MR
3133:,
3119:,
3096:;
3019:41
3017:,
3009:;
3005:;
2969:MR
2965:17
2963:,
2954:.
2947:MR
2945:,
2937:,
2927:42
2925:,
2893:^
2860:;
2827:,
2821:MR
2819:,
2805:,
2788:,
2780:,
2766:,
2760:,
2752:;
2748:;
2744:;
2706:,
2700:MR
2698:,
2684:,
2680:,
2657:^
2648:;
2605:MR
2603:,
2530:,
2513:,
2489:^
2476:;
2472:;
2462:^
2445:^
2430:^
2276:.
2046:.
2025:=
2018:wx
2014:uv
1942:1,
1881:.
1793:.
1453:=
1410:.
961:.
878:,2
872:KG
717:.
423:.
208:.
170:.
111:.
105:L(
93:L(
81:L(
65:L(
4336:.
4302:.
4289::
4283:7
4260::
4254:9
4240:.
4219:.
4204::
4196::
4177:.
4156::
4140:.
4119::
4103:.
4090::
4072:.
4055:.
4034::
4018:.
4005::
3999:2
3989:G
3985:H
3981:n
3979:,
3977:m
3971:.
3956::
3946::
3924:.
3903::
3895::
3885::
3865:.
3860::
3840:.
3825::
3807:.
3784::
3766:.
3745:.
3724::
3706:.
3696:.
3665:.
3650::
3642::
3636:9
3621:.
3606::
3600:2
3590:.
3577::
3569::
3559::
3541:.
3528::
3520::
3510::
3492:.
3479::
3467:.
3444::
3432:.
3417::
3411:9
3399:.
3378:.
3358::
3336:.
3324:.
3312:.
3300:.
3288:.
3262:.
3239:.
3214:.
3189:.
3168::
3160::
3142:.
3127::
3100:.
3084:.
3068:.
3044:.
3032:.
3025::
2992:.
2976:.
2933::
2888:.
2876:.
2864:.
2836:.
2813::
2784::
2774::
2692::
2652:.
2636:.
2534:.
2484:.
2417:)
2415:G
2413:(
2411:L
2406:)
2404:G
2402:(
2400:D
2391:)
2389:G
2387:(
2385:L
2376:)
2374:G
2372:(
2370:D
2365:)
2363:G
2361:(
2359:D
2350:G
2346:)
2344:G
2342:(
2340:D
2335:G
2331:)
2329:G
2327:(
2325:D
2320:G
2274:G
2270:)
2268:G
2266:(
2264:L
2259:G
2255:G
2251:)
2249:G
2247:(
2245:L
2240:G
2234:k
2228:e
2224:d
2220:)
2218:G
2216:(
2214:L
2209:k
2205:v
2201:G
2197:e
2193:d
2185:G
2181:)
2179:G
2177:(
2175:L
2170:)
2168:k
2166:(
2164:O
2159:)
2157:k
2155:(
2153:O
2148:G
2144:e
2140:f
2136:v
2132:)
2130:G
2128:(
2126:L
2121:v
2117:e
2113:f
2109:e
2105:G
2097:)
2095:G
2093:(
2091:L
2086:G
2080:k
2078:(
2076:k
2071:G
2067:k
2063:)
2061:G
2059:(
2057:L
2036:G
2032:G
2027:w
2023:v
2010:G
2006:x
2002:w
1998:v
1994:u
1990:G
1978:G
1944:n
1939:K
1930:G
1926:G
1910:G
1906:G
1902:G
1898:)
1896:G
1894:(
1892:T
1844:K
1839:)
1837:G
1835:(
1833:L
1828:G
1820:G
1791:G
1787:G
1778:.
1768:G
1761:)
1759:G
1757:(
1755:L
1746:K
1741:G
1736:.
1734:G
1730:)
1728:G
1726:(
1724:L
1719:G
1711:)
1709:G
1707:(
1705:L
1696:G
1684:G
1664:.
1658:,
1655:)
1652:)
1649:)
1646:G
1643:(
1640:L
1637:(
1634:L
1631:(
1628:L
1625:,
1622:)
1619:)
1616:G
1613:(
1610:L
1607:(
1604:L
1601:,
1598:)
1595:G
1592:(
1589:L
1586:,
1583:G
1555:v
1551:S
1543:G
1539:v
1535:G
1527:S
1523:L
1519:v
1515:G
1511:S
1507:G
1503:L
1499:v
1487:G
1483:)
1481:G
1479:(
1477:L
1472:v
1465:G
1461:)
1459:G
1457:(
1455:L
1451:L
1446:G
1442:L
1438:L
1381:K
1329:G
1325:L
1321:L
1317:G
1313:G
1309:L
1305:G
1301:L
1297:L
1293:L
1289:L
1285:L
1278:G
1274:)
1272:G
1270:(
1268:L
1263:)
1261:G
1259:(
1257:L
1252:)
1250:G
1248:(
1246:L
1237:v
1233:G
1229:v
1225:G
1195:I
1191:A
1186:I
1182:J
1168:I
1165:2
1159:J
1153:T
1148:J
1144:=
1141:A
1131:A
1127:A
1094:G
1086:)
1084:G
1082:(
1080:L
1057:n
1052:K
1046:4
1043:K
1026:)
1024:G
1022:(
1020:L
1011:G
1000:)
995:K
993:(
991:L
959:)
957:8
954:K
952:(
950:L
937:)
935:8
932:K
930:(
928:L
921:n
917:n
913:n
911:(
909:n
898:8
895:K
888:n
876:n
858:n
856:(
854:J
841:n
839:K
807:K
794:K
782:K
776:3
773:K
761:K
752:3
749:K
693:G
689:G
681:G
677:G
669:G
662:)
660:G
658:(
656:L
651:G
630:.
628:)
626:G
624:(
622:L
613:G
604:.
602:G
594:)
592:G
590:(
588:L
579:G
571:)
569:G
567:(
565:L
556:G
548:)
546:G
544:(
542:L
532:.
530:m
526:G
518:)
516:G
514:(
512:L
507:m
503:)
501:G
499:(
497:L
492:m
488:n
484:G
466:G
462:)
460:G
458:(
456:L
451:)
449:G
447:(
445:L
436:G
417:)
415:G
413:(
411:L
406:G
398:)
396:G
394:(
392:L
387:G
370:)
368:G
354:)
352:G
337:G
333:G
318:G
293:G
283:.
281:G
273:)
271:G
269:(
267:L
259:G
255:)
253:G
251:(
249:L
236:)
234:G
232:(
230:L
225:G
185:G
109:)
107:G
101:G
97:)
95:G
89:G
85:)
83:G
77:G
69:)
67:G
61:G
41:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
