Grafico a linee - Line graph

Nella matematica disciplina della teoria dei grafi , il grafico lineare di un grafo non orientato G è un altro grafico L ( G ) che rappresenta le adiacenze tra bordi di G . L( G ) si costruisce nel modo seguente: per ogni arco in G , crea un vertice in L( G ); per ogni due archi in G che hanno un vertice in comune, crea un arco tra i loro vertici corrispondenti in L( G ).

Il grafico a linee del nome deriva da un articolo di Harary & Norman (1960) sebbene sia Whitney (1932) che Krausz (1943) abbiano utilizzato la costruzione prima di questa. Altri termini usati per il grafico a linee includono il grafico di copertura , la derivata , il duale da bordo a vertice , il coniugato , il grafico rappresentativo e il -obrazom , nonché il grafico del bordo , il grafico di interscambio , il grafico aggiunto e il grafico derivato .

Hassler Whitney ( 1932 ) dimostrò che con un caso eccezionale la struttura di un grafo connesso G può essere completamente recuperata dal suo grafo lineare. Molte altre proprietà dei grafici a linee seguono traducendo le proprietà del grafo sottostante dai vertici ai bordi, e per il teorema di Whitney la stessa traslazione può essere eseguita anche nell'altra direzione. I grafici a linee sono privi di artigli e i grafici a linee dei grafici bipartiti sono perfetti . I grafici a linee sono caratterizzati da nove sottografi proibiti e possono essere riconosciuti in tempo lineare .

Sono state studiate varie estensioni del concetto di grafico a linee, inclusi grafici a linee di grafici a linee, grafici a linee di multigrafi, grafici a linee di ipergrafi e grafici a linee di grafici ponderati.

Definizione formale

Dato un grafo G , il suo grafo lineare L ( G ) è un grafo tale che

ogni vertice di L ( G ) rappresenta un arco di G ; e
due vertici di L ( G ) sono adiacenti se e solo se i loro archi corrispondenti condividono un punto finale comune ("sono incidenti") in G .

Cioè, è il grafico di intersezione degli archi di G , che rappresenta ciascun arco dall'insieme dei suoi due estremi.

Esempio

Le figure seguenti mostrano un grafico (a sinistra, con vertici blu) e il suo grafico a linee (a destra, con vertici verdi). Ogni vertice del grafico a linee è mostrato etichettato con la coppia di punti finali del bordo corrispondente nel grafico originale. Ad esempio, il vertice verde a destra etichettato 1,3 corrisponde al bordo a sinistra tra i vertici blu 1 e 3. Il vertice verde 1,3 è adiacente ad altri tre vertici verdi: 1,4 e 1,2 (corrispondenti agli archi che condividono l'estremo 1 nel grafico blu) e 4,3 (corrispondente a un arco che condivide l'estremo 3 nel grafico blu).

Grafico G
Vertici in L(G) costruiti da spigoli in G
Bordi aggiunti in L(G)
Il grafico a linee L(G)

Proprietà

Proprietà tradotte del grafico sottostante

Le proprietà di un grafo G che dipendono solo dall'adiacenza tra gli spigoli possono essere tradotte in proprietà equivalenti in L ( G ) che dipendono dall'adiacenza tra i vertici. Ad esempio, un matching in G è un insieme di archi di cui non due sono adiacenti, e corrisponde a un insieme di vertici in L ( G ) di cui due non sono adiacenti, cioè un insieme indipendente .

Così,

Il grafico a linee di un grafico connesso è connesso. Se G è connesso, contiene un percorso che collega due dei suoi bordi, che si traduce in un percorso in L ( G ) contenente due dei vertici di L ( G ). Tuttavia, un grafo G che ha alcuni vertici isolati, ed è quindi disconnesso, può comunque avere un grafo a linee connesso.
Un grafico a linee ha un punto di articolazione se e solo se il grafico sottostante ha un ponte per il quale nessuno dei due estremi ha grado uno.
Per un grafo G con n vertici e m archi, il numero di vertici del grafo lineare L ( G ) è m , e il numero di archi di L ( G ) è metà della somma dei quadrati dei gradi dei vertici in G , meno m .
Un insieme indipendente in L( G ) corrisponde a un matching in G . In particolare, un massimo insieme indipendente in L( G ) corrisponde al massimo matching in G . Poiché i matching massimi possono essere trovati in tempo polinomiale, così possono essere i massimi insiemi indipendenti di grafici lineari, nonostante la durezza del problema dei massimi insiemi indipendenti per famiglie di grafi più generali. Allo stesso modo, un insieme indipendente dall'arcobaleno in L ( G ) corrisponde a un abbinamento arcobaleno in G .
Il numero cromatico degli spigoli di un grafo G è uguale al numero cromatico dei vertici del suo grafo a linee L ( G ).
Il grafico lineare di un grafo transitivo sugli archi è transitivo sui vertici . Questa proprietà può essere utilizzata per generare famiglie di grafi che (come il grafo di Petersen ) sono transitivi ai vertici ma non sono grafici di Cayley : se G è un grafo transitivo sugli archi che ha almeno cinque vertici, non è bipartito e ha un vertice dispari gradi, allora L ( G ) è un grafo non di Cayley transitivo ai vertici.
Se un grafo G ha un ciclo di Eulero , cioè se G è connesso e ha un numero pari di archi in ogni vertice, allora il grafo lineare di G è hamiltoniano . Tuttavia, non tutti i cicli hamiltoniani nei grafici a linee derivano in questo modo dai cicli di Eulero; per esempio, il grafo lineare di un grafo hamiltoniano G è esso stesso hamiltoniano, indipendentemente dal fatto che G sia anche euleriano.
Se due grafi semplici sono isomorfi, anche i loro grafici a linee sono isomorfi. Il teorema dell'isomorfismo del grafo di Whitney fornisce un contrario per tutti tranne una coppia di grafi.
Nel contesto della teoria delle reti complesse, il grafico a linee di una rete casuale conserva molte delle proprietà della rete come la proprietà del piccolo mondo (l'esistenza di brevi cammini tra tutte le coppie di vertici) e la forma della sua distribuzione dei gradi . Evans e Lambiotte (2009) osservano che qualsiasi metodo per trovare cluster di vertici in una rete complessa può essere applicato al grafico a linee e utilizzato invece per raggruppare i suoi bordi.

Teorema dell'isomorfismo di Whitney

Il grafo del diamante , un'eccezione al teorema di Whitney forte

Se i grafici lineari di due grafi collegati sono isomorfi, allora i grafici sottostanti sono isomorfi, tranne nel caso del grafo triangolare K ₃ e dell'artiglio K _1,3 , che hanno grafici lineari isomorfi ma non sono essi stessi isomorfi.

Oltre a K ₃ e K _1,3 , ci sono altri piccoli grafici eccezionali con la proprietà che il loro grafico lineare ha un grado di simmetria più elevato rispetto al grafico stesso. Ad esempio, il grafo del diamante K _1,1,2 (due triangoli che condividono un bordo) ha quattro automorfismi di grafo ma il suo grafo lineare K _{1,2,2 ne} ha otto. Nell'illustrazione del grafico a diamante mostrato, la rotazione del grafico di 90 gradi non è una simmetria del grafico, ma è una simmetria del suo grafico a linee. Tuttavia, tutti questi casi eccezionali hanno al massimo quattro vertici. Una versione rafforzata del teorema dell'isomorfismo di Whitney afferma che, per grafi connessi con più di quattro vertici, esiste una corrispondenza biunivoca tra gli isomorfismi dei grafi e gli isomorfismi dei loro grafici a linee.

Analoghi del teorema dell'isomorfismo di Whitney sono stati dimostrati per i grafici lineari dei multigrafi , ma in questo caso sono più complicati.

Grafici a linee fortemente regolari e perfetti

Un grafico a linee perfette. I bordi in ogni componente biconnesso sono colorati di nero se il componente è bipartito, blu se il componente è un tetraedro e rosso se il componente è un libro di triangoli.

Il grafo lineare del grafo completo K _n è anche noto come grafo triangolare , grafo di Johnson J ( n , 2) o complemento del grafo di Kneser KG _{n ,2} . I grafi triangolari sono caratterizzati dai loro spettri , eccetto n = 8. Possono anche essere caratterizzati (sempre con l'eccezione di K ₈ ) come i grafi fortemente regolari con parametri srg( n ( n − 1)/2, 2( n − 2), n − 2, 4). I tre grafici fortemente regolari con gli stessi parametri e spettro di L ( K ₈ ) sono i grafici di Chang , che possono essere ottenuti commutando il grafico da L ( K ₈ ).

Il grafo a linee di un grafo bipartito è perfetto (vedi il teorema di Kőnig ), ma non è necessario che sia bipartito come mostra l'esempio del grafo ad artiglio. I grafici lineari dei grafi bipartiti costituiscono uno degli elementi chiave dei grafi perfetti, utilizzati nella dimostrazione del teorema del grafo perfetto forte . Un caso speciale di questi grafici sono i grafici della torre, grafici a linee di grafi bipartiti completi . Come i grafici a linee di grafici completi, possono essere caratterizzati con un'eccezione dal numero di vertici, numero di bordi e numero di vicini condivisi per punti adiacenti e non adiacenti. L'unico caso eccezionale è L ( K _4,4 ), che condivide i suoi parametri con il grafico Shrikhande . Quando entrambi i lati della bipartizione hanno lo stesso numero di vertici, questi grafici sono di nuovo fortemente regolari.

Più in generale, si dice che un grafo G è un grafo a linee perfette se L ( G ) è un grafo perfetto . I grafici lineari perfetti sono esattamente i grafici che non contengono un ciclo semplice di lunghezza dispari maggiore di tre. Equivalentemente, un grafo è retta perfetta se e solo se ciascuna delle sue componenti biconnesse è bipartita o della forma K ₄ (il tetraedro) o K _{1,1, n} (un libro di uno o più triangoli che condividono tutti un bordo comune) . Ogni grafico a linee perfette è di per sé perfetto.

Altre famiglie di grafici correlati

Tutti i grafici a linee sono grafici senza artigli , grafici senza un sottografo indotto nella forma di un albero a tre foglie. Come con i grafi senza claw più in generale, ogni grafo a linee connesse L ( G ) con un numero pari di archi ha un matching perfetto ; equivalentemente, questo significa che se il grafo sottostante G ha un numero pari di archi, i suoi archi possono essere partizionati in cammini a due archi.

I grafici lineari degli alberi sono esattamente i grafici a blocchi senza artigli . Questi grafi sono stati usati per risolvere un problema nella teoria dei grafi estremali , di costruire un grafo con un dato numero di archi e vertici il cui albero più grande indotto come sottografo sia il più piccolo possibile.

Tutti gli autovalori della matrice di adiacenza di un grafico a linee sono almeno -2. La ragione di ciò è che può essere scritto come , dove è la matrice di incidenza senza segno del grafico prelineare ed è l'identità. In particolare, è la matrice Gramiana di un sistema di vettori: tutti i grafi con questa proprietà sono stati chiamati grafi lineari generalizzati. $A$ $A$ $A=J^{\mathsf {T}}J-2I$ $J$ $io$ $A+2I$

Caratterizzazione e riconoscimento

partizione cricca

Partizione di un grafico a linee in cricche

Per un grafo arbitrario G , e un vertice arbitrario v in G , l'insieme degli archi incidenti a v corrisponde a una cricca nel grafo a linee L ( G ). Le cricche così formate suddividono gli spigoli di L ( G ). Ciascun vertice di L ( G ) appartiene esattamente a due di essi (le due cricche corrispondenti ai due estremi dello spigolo corrispondente in G ).

L'esistenza di una tale partizione in cricche può essere utilizzata per caratterizzare i grafi a linee: Un grafo L è il grafo a linee di qualche altro grafo o multigrafo se e solo se è possibile trovare un insieme di cricche in L (consentendo alcuni dei cricche per essere singoli vertici) che dividono gli spigoli di L , in modo tale che ogni vertice di L appartenga esattamente a due delle cricche. È il grafico a linee di un grafo (piuttosto che un multigrafo) se questo insieme di cricche soddisfa la condizione aggiuntiva che nessun due vertici di L sono entrambi nelle stesse due cricche. Data una tale famiglia di cricche, il grafo sottostante G per il quale L è il grafo lineare può essere recuperato creando un vertice in G per ogni cricca e un arco in G per ogni vertice in L con i suoi estremi essendo le due cricche contenenti la vertice in L . Per la versione forte del teorema di isomorfismo di Whitney, se il grafo sottostante G ha più di quattro vertici, può esserci solo una partizione di questo tipo.

Ad esempio, questa caratterizzazione può essere utilizzata per mostrare che il grafico seguente non è un grafico a linee:

In questo esempio, i bordi che vanno verso l'alto, a sinistra ea destra dal vertice centrale di grado quattro non hanno cricche in comune. Pertanto, qualsiasi partizione dei bordi del grafo in cricche dovrebbe avere almeno una cricca per ciascuno di questi tre bordi, e queste tre cricche si intersecherebbero tutte in quel vertice centrale, violando il requisito che ogni vertice appaia esattamente in due cricche. Pertanto, il grafico mostrato non è un grafico a linee.

Sottografi proibiti

I nove grafi minimi non lineari, dalla caratterizzazione di sottografi proibiti di Beineke dei grafici lineari. Un grafico è un grafico a linee se e solo se non contiene uno di questi nove grafici come sottografo indotto.

Un'altra caratterizzazione dei grafici a linee è stata dimostrata in Beineke (1970) (e riportata in precedenza senza dimostrazione da Beineke (1968) ). Ha mostrato che ci sono nove grafici minimi che non sono grafici a linee, in modo tale che ogni grafico che non è un grafico a linee ha uno di questi nove grafici come sottografo indotto . Cioè, un grafo è un grafo a linee se e solo se nessun sottoinsieme dei suoi vertici induce uno di questi nove grafi. Nell'esempio sopra, i quattro vertici più alti inducono un artiglio (cioè un grafo bipartito completo K _1,3 ), mostrato in alto a sinistra nell'illustrazione dei sottografi proibiti. Pertanto, per la caratterizzazione di Beineke, questo esempio non può essere un grafico a linee. Per i grafici con grado minimo almeno 5, nella caratterizzazione sono necessari solo i sei sottografi nelle colonne sinistra e destra della figura.

Algoritmi

Roussopoulos (1973) e Lehot (1974) hanno descritto algoritmi di tempo lineare per riconoscere i grafici a linee e ricostruire i loro grafici originali. Sysło (1982) ha generalizzato questi metodi ai grafi orientati . Degiorgi & Simon (1995) hanno descritto una struttura dati efficiente per mantenere un grafo dinamico, soggetto a inserimenti e cancellazioni di vertici, e mantenere una rappresentazione dell'input come un grafico a linee (quando esiste) nel tempo proporzionale al numero di archi modificati a ogni passo.

Gli algoritmi di Roussopoulos (1973) e Lehot (1974) si basano su caratterizzazioni di grafici lineari che coinvolgono triangoli dispari (triangoli nel grafico lineare con la proprietà che esiste un altro vertice adiacente a un numero dispari di vertici triangolari). Tuttavia, l'algoritmo di Degiorgi & Simon (1995) utilizza solo il teorema di isomorfismo di Whitney. È complicato dalla necessità di riconoscere le eliminazioni che fanno sì che il grafico rimanente diventi un grafico a linee, ma quando è specializzato nel problema di riconoscimento statico è necessario eseguire solo inserimenti e l'algoritmo esegue i seguenti passaggi:

Costruisci il grafico di input L aggiungendo vertici uno alla volta, scegliendo ad ogni passo un vertice da aggiungere adiacente ad almeno un vertice precedentemente aggiunto. Mentre si aggiungono vertici a L , mantenere un grafo G per cui L = L ( G ); se l'algoritmo non riesce mai a trovare un grafo appropriato G , allora l'input non è un grafico a linee e l'algoritmo termina.
Quando si aggiunge un vertice v a un grafo L ( G ) per il quale G ha quattro o meno vertici, potrebbe essere il caso che la rappresentazione del grafico a linee non sia univoca. Ma in questo caso, il grafo aumentato è abbastanza piccolo da poterne trovare una rappresentazione come grafico a linee mediante una ricerca a forza bruta in tempo costante.
Quando si aggiunge un vertice v a un grafo L più grande che è uguale al grafo lineare di un altro grafo G , sia S il sottografo di G formato dagli archi che corrispondono ai vicini di v in L . Verificare che S abbia una copertura dei vertici costituita da un vertice o da due vertici non adiacenti. Se ci sono due vertici nella copertura, aumenta G aggiungendo un bordo (corrispondente a v ) che collega questi due vertici. Se c'è un solo vertice nella copertura, aggiungi un nuovo vertice a G , adiacente a questo vertice.

Ogni passo richiede tempo costante o implica la ricerca di una copertura di vertici di dimensione costante all'interno di un grafo S la cui dimensione è proporzionale al numero di vicini di v . Pertanto, il tempo totale per l'intero algoritmo è proporzionale alla somma dei numeri dei vicini di tutti i vertici, che (per il lemma dell'handshaking ) è proporzionale al numero di archi in ingresso.

Iterazione dell'operatore grafico a linee

van Rooij & Wilf (1965) considerano la sequenza dei grafici

G,L(G),L(L(G)),L(L(L(G))),\dots .\

Mostrano che, quando G è un grafo connesso finito , sono possibili solo quattro comportamenti per questa sequenza:

Se G è un grafo di cicli, allora L ( G ) e ogni grafo successivo in questa sequenza sono isomorfi a G stesso. Questi sono gli unici grafi connessi per i quali L ( G ) è isomorfo a G .
Se G è un artiglio K _1,3 , allora L ( G ) e tutti i grafici successivi nella sequenza sono triangoli.
Se G è un grafo del percorso, allora ogni grafo successivo nella sequenza è un percorso più breve fino a quando la sequenza termina con un grafo vuoto .
In tutti i restanti casi, le dimensioni dei grafici in questa sequenza alla fine aumentano senza limiti.

Se G non è connesso, questa classificazione si applica separatamente a ciascun componente di G .

Per i grafi connessi che non sono cammini, tutti i numeri sufficientemente alti di iterazioni dell'operazione del grafico a linee producono grafi che sono hamiltoniani.

generalizzazioni

Grafici mediali e poliedri convessi

Quando un grafo planare G ha grado massimo di vertice tre, il suo grafico lineare è planare e ogni immersione planare di G può essere estesa a un'immersione di L ( G ). Tuttavia, esistono grafici planari con grado più elevato i cui grafici a linee sono non planari. Questi includono, ad esempio, il 5-star K _1,5 , il grafico della gemma formato dall'aggiunta di due diagonali non incrociate all'interno di un pentagono regolare e tutti i poliedri convessi con un vertice di grado quattro o più.

Una costruzione alternativa, il grafico mediale , coincide con il grafico a linee per i grafici planari con grado massimo tre, ma è sempre planare. Ha gli stessi vertici del grafo lineare, ma potenzialmente meno spigoli: due vertici del grafo mediale sono adiacenti se e solo se i due spigoli corrispondenti sono consecutivi su qualche faccia dell'immersione planare. Il grafico mediale del grafico duale di un grafico piano è lo stesso del grafico mediale del grafico piano originale.

Per poliedri regolari o poliedri semplici, l'operazione del grafico mediale può essere rappresentata geometricamente dall'operazione di tagliare ciascun vertice del poliedro da un piano passante per i punti medi di tutti i suoi bordi incidenti. Questa operazione è nota in vari modi come secondo troncamento, troncamento degenerato o rettifica .

Grafici totali

Il grafo totale T ( G ) di un grafo G ha come vertici gli elementi (vertici o archi) di G , e ha un arco tra due elementi ogni volta che sono incidenti o adiacenti. Il grafico totale può essere ottenuto anche suddividendo ciascun arco di G e quindi prendendo il quadrato del grafico suddiviso.

Multigrafi

Il concetto di grafico a linee di G può naturalmente essere esteso al caso in cui G sia un multigrafo. In questo caso, le caratterizzazioni di questi grafici possono essere semplificate: la caratterizzazione in termini di partizioni di cricca non deve più impedire che due vertici appartengano alle cricche e la caratterizzazione di grafi proibiti ha sette grafi proibiti invece di nove.

Tuttavia, per i multigrafi, esiste un numero maggiore di coppie di grafici non isomorfi che hanno gli stessi grafici a linee. Ad esempio un grafo bipartito completo K _{1, n} ha lo stesso grafo a linee del grafo dipolo e multigrafo di Shannon con lo stesso numero di archi. Tuttavia, in questo caso possono ancora essere derivati analoghi al teorema di isomorfismo di Whitney.

Digrafi lineari

Costruzione dei grafici di de Bruijn come digrafi a linee iterate

È anche possibile generalizzare grafici lineari a grafici orientati. Se G è un grafo orientato, il suo grafico lineare o digrafo lineare ha un vertice per ogni arco di G . Due vertici che rappresentano archi diretti da u a ve da w a x in G sono collegati da un arco da uv a wx nel digrafo lineare quando v = w . Cioè, ogni arco nel digrafo lineare di G rappresenta un cammino diretto di lunghezza due in G . I grafi di de Bruijn possono essere formati ripetendo questo processo di formazione di grafi a linee orientate, partendo da un grafo orientato completo .

Grafici a linee ponderate

In un grafo a linee L ( G ), ogni vertice di grado k nel grafo originale G crea k ( k − 1)/2 archi nel grafo a linee. Per molti tipi di analisi ciò significa che i nodi di alto grado in G sono sovrarappresentati nel grafico a linee L ( G ). Ad esempio, considera una passeggiata casuale sui vertici del grafo originale G . Questo passerà lungo un bordo e con una certa frequenza f . D'altra parte, questo arco e è mappato su un unico vertice, diciamo v , nel grafico a linee L ( G ). Se ora eseguiamo lo stesso tipo di random walk sui vertici del grafico a linee, la frequenza con cui v viene visitata può essere completamente diversa da f . Se il nostro arco e in G era connesso a nodi di grado O( k ), sarà attraversato più frequentemente O( k ² ) nel grafo lineare L ( G ). In altre parole, il teorema dell'isomorfismo del grafo di Whitney garantisce che il grafo a linee quasi sempre codifica fedelmente la topologia del grafo originale G, ma non garantisce che le dinamiche su questi due grafi abbiano una relazione semplice. Una soluzione è costruire un grafico a linee ponderate, ovvero un grafico a linee con bordi ponderati . Ci sono diversi modi naturali per farlo. Ad esempio se gli archi d ed e nel grafo G sono incidenti in un vertice v con grado k , allora nel grafo lineare L ( G ) l'arco che collega i due vertici d ed e può avere peso 1/( k − 1) . In questo modo ogni arco in G (ammesso che nessuna delle due estremità sia collegata ad un vertice di grado 1) avrà forza 2 nel grafico a linee L ( G ) corrispondente alle due estremità che l'arco ha in G . È semplice estendere questa definizione di grafico a linee ponderate ai casi in cui il grafico originale G era diretto o addirittura ponderato. Il principio in tutti i casi è garantire che il grafo lineare L ( G ) rifletta la dinamica e la topologia del grafo originale G .

Grafici a linee di ipergrafi

I bordi di un ipergrafo possono formare una famiglia arbitraria di insiemi , quindi il grafico a linee di un ipergrafo è lo stesso del grafico di intersezione degli insiemi della famiglia.

Grafico di disgiunzione

Il grafo di disgiunzione di G , indicato con D( G ), è costruito nel modo seguente: per ogni arco in G , crea un vertice in D( G ); per ogni due archi in G che non hanno un vertice in comune, crea un arco tra i loro vertici corrispondenti in D( G ). In altre parole, D( G ) è il grafo complementare di L( G ). Una cricca in D( G ) corrisponde a un insieme indipendente in L( G ), e viceversa.

Appunti

Riferimenti

Beineke, LW (1968), "Grafici derivati di digrafi", in Sachs, H.; Voss, H.-J.; Walter, H.-J. (a cura di), Beiträge zur Graphentheorie , Lipsia: Teubner, pp. 17-33.
Beineke, LW (1970), "Caratterizzazioni di grafici derivati", Journal of Combinatorial Theory , 9 (2): 129–135, doi : 10.1016/S0021-9800(70)80019-9 , MR 0262097.
Cvetković, Dragoš; Rowlinson, Pietro; Simić, Slobodan (2004), Generalizzazioni spettrali dei grafici a linee , London Mathematical Society Lecture Note Series, 314 , Cambridge: Cambridge University Press, doi : 10.1017/CBO9780511751752 , ISBN 0-521-83663-8, MR 2120511.
Degiorgi, Daniele Giorgio; Simon, Klaus (1995), "Un algoritmo dinamico per il riconoscimento di grafici a linee", Concetti teorici dei grafi in informatica (Aachen, 1995) , Lecture Notes in Computer Science, 1017 , Berlin: Springer, pp. 37-48, doi : 10.1007/3-540-60618-1_64 , MR 1400011.
Evans, ST; Lambiotte, R. (2009), "Grafici lineari, partizioni di collegamento e comunità sovrapposte", Physical Review E , 80 (1): 016105, arXiv : 0903.2181 , Bibcode : 2009PhRvE..80a6105E , doi : 10.1103/PhysRevE.80.016105 , PMID 19658772.
Evans, ST; Lambiotte, R. (2010), "Grafici lineari di reti ponderate per comunità sovrapposte", European Physical Journal B , 77 (2): 265–272, arXiv : 0912.4389 , Bibcode : 2010EPJB...77..265E , doi : 10.1140/epjb/e2010-00261-8 , S2CID 119504507.
Greenwell, DL; Hemminger, Robert L. (1972), "Sottografi proibiti per grafici con grafici a linee planari", Matematica discreta , 2 : 31–34, doi : 10.1016/0012-365X(72)90058-1 , MR 0297604.
Harary, F. ; Norman, RZ (1960), "Alcune proprietà dei digrafi lineari", Rendiconti del Circolo Matematico di Palermo , 9 (2): 161-169, doi : 10.1007/BF02854581 , hdl : 10338.dmlcz/128114 , S2CID 122473974.
Harary, F. (1972), "8. Grafici lineari", Teoria dei grafi (PDF) , Massachusetts: Addison-Wesley, pp. 71-83.
Hemminger, RL; Beineke, LW (1978), "Grafici lineari e digrafi lineari", in Beineke, LW; Wilson, RJ (a cura di), Argomenti selezionati in teoria dei grafi , Academic Press Inc., pp. 271-305.
Jung, HA (1966), "Zu einem Isomorphiesatz von H. Whitney für Graphen", Mathematische Annalen (in tedesco), 164 : 270–271, doi : 10.1007/BF01360250 , MR 0197353 , S2CID 119898359.
Krausz, J. (1943), "Démonstration nouvelle d'un théorème de Whitney sur les réseaux", Mat. Fiz. Lapok , 50 : 75–85, MR 0018403.
Lehot, Philippe GH (1974), "Un algoritmo ottimale per rilevare un grafico a linee e produrre il suo grafico radice", Journal of the ACM , 21 (4): 569–575, doi : 10.1145/321850.321853 , MR 0347690 , S2CID 15036484.
Maffray, Frédéric (1992), "Kernels in perfect line-graphs", Journal of Combinatorial Theory , Serie B, 55 (1): 1–8, doi : 10.1016/0095-8956(92)90028-V , MR 1159851.
Metelsky, Yury; Tyshkevich, Regina (1997), "Grafici in linea di ipergrafi lineari 3-uniformi", Journal of Graph Theory , 25 (4): 243-251, doi : 10.1002/(SICI) 1097-0118 (199708) 25: 4 < 243::AID-JGT1>3.0.CO;2-K.
Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003), "Generazione di reti correlate da quelle non correlate" , Phys. Rev. E , 67 (4): 046107, arXiv : cond-mat/0212469 , Bibcode : 2003PhRvE..67d6107R , doi : 10.1103/physreve.67.046107 , PMID 12786436 , S2CID 33054818.
van Rooij, ACM; Wilf, HS (1965), "Il grafico di interscambio di un grafico finito", Acta Mathematica Hungarica , 16 (3-4): 263-269, doi : 10.1007/BF01904834 , hdl : 10338.dmlcz/140421 , S2CID 122866512.
Roussopoulos, ND (1973), "A max { m , n } algoritmo per determinare il grafico H dal suo grafico lineare G ", Information Processing Letters , 2 (4): 108–112, doi : 10.1016/0020-0190(73 ) 90029-X , MR 0.424.435.
Ryjáček, Zdeněk; Vrána, Petr (2011), "Grafici lineari di multigrafi e connessione Hamilton di grafici privi di artigli", Journal of Graph Theory , 66 (2): 152-173, doi : 10.1002/jgt.20498 , MR 2778727.
Sedláček, J. (1964), "Alcune proprietà dei grafici di interscambio", Teoria dei grafi e sue applicazioni (Proc. Sympos. Smolenice, 1963) , Publ. Casa cecoslovacca Acad. Sci., Praga, pp. 145-150, MR 0173255.
Sysło, Maciej M. (1982), "Un algoritmo di etichettatura per riconoscere un digrafo lineare e produrre il suo grafico radice", Lettere per l'elaborazione delle informazioni , 15 (1): 28–30, doi : 10.1016/0020-0190(82)90080- 1 , MR 0678028.
Trotter, LE, Jr. (1977), "Grafici lineari perfetti", Programmazione matematica , 12 (2): 255–259, doi : 10.1007/BF01593791 , MR 0457293 , S2CID 38906333.
de Werra, D. (1978), "Grafici perfetti in linea", Programmazione matematica , 15 (2): 236–238, doi : 10.1007/BF01609025 , MR 0509968 , S2CID 37062237.
Whitney, H. (1932), "Grafici congruenti e connettività dei grafici", American Journal of Mathematics , 54 (1): 150–168, doi : 10.2307/2371086 , hdl : 10338.dmlcz/101067 , JSTOR 2371086.
Zhang, Fu Ji; Lin, Guo Ning (1987), "Sui grafici de Bruijn-Good", Acta Math. Sinica , 30 (2): 195-205, MR 0891925.
верович, И. . (1997), Per saperne di più, Diskretnaya Matematika (in russo), 9 (2): 98–105, doi : 10.4213/dm478 , MR 1468075. Tradotto in inglese come Zverovich, I. È. (1997), "Un analogo del teorema di Whitney per i grafici dei bordi dei multigrafi e dei multigrafi dei bordi", Matematica e applicazioni discrete , 7 (3): 287–294, doi : 10.1515/dma.1997.7.3.287 , S2CID 120525090.

Languages

In other projects