Vi anser att en generalisering av skärningspunkter grafer av stigar i ett träd. Låt P vara en samling av icke-triviala enkla stigar i ett träd T. Vi definierar k-kanten (k 1) skärningskurva k (P), vars hörn motsvarar medlemmarna i P, och två hörn förenas av en kant om motsvarande medlemmar av P dela k kanter i T. En oriktad graf G kallas en k-kant skärningskurva av stigar i ett träd, och betecknas av k-EPT, om G = k (P) för vissa P och T. Det är känt att igenkännandet och färgningen av 1-EPT grafer är NP-fullständig. Vi utökar detta resultat och bevisar att igenkänningen och färgningen av k-EPT-graferna är NP-kompletterade för alla fasta k 1. Vi visar att problemet med att hitta den största klicken på k-EPT grafer är polynom, som var fallet för 1-EPT grafer, och avgöra att det finns som mest O(n 3 ) maximal klick i en k-EPT graf på n hörn. Vi bevisar att familjen av 1-EPT grafer finns i, men är inte lika med, familjen av k-EPT grafer för alla fasta k 2. Vi undersöker också de hierarkiska sambanden mellan relaterade klasser av grafer, och presenterar en oändlig familj av grafer som inte är k-EPT grafer för varje k 2. Graferna för skärningspunktens kant används i nätverksapplikationer. Schemaläggning oriktade anrop i ett träd är detsamma som att färglägga en skärningskurva över stigar i ett träd. Att tilldela våglängder till virtuella anslutningar i ett optiskt nätverk är också detsamma som att färga en kant skärningskurva över stigar i ett träd.
De k-kant skärningsdiagram där två hörn är intilliggande om deras motsvarande vägar skär på minst k kanter studeras i REF.
The k-edge intersection graphs of paths in a tree
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}