Povzetek
Kartezični produkti polnih grafov so znani kot Hammingovi grafi. Z uporabo vložitev v kartezične produkte kvocientnih grafov so karakterizirani podgrafi, inducirani podgrafi in izometrični podgrafi Hammingovih grafov. Na primer, graf ▫$G$▫ je inducirani podgraf Hammingovega grafa natanko tedaj, ko obstaja označitev povezav grafa ▫$G$▫, ki zadošča naslednjima pogojema: (i) povezave trikotnika imajo isto oznako, (ii) za vsaki točki ▫$u$▫ in ▫$v$▫ na razdalji vsaj 2 obstajata dve taki oznaki, ki se pojavita na vsaki inducirani poti med ▫$u$▫ in ▫$v$▫.
Ključne besede
matematika;teorija grafov;Hammingovi grafi;inducirani podgrafi;izometrični podgrafi;kartezični produkt grafov;označevanje povezav;kvocientni grafi;ne zaključna dela;mathematics;graph theory;Hamming graphs;induced subgraphs;isometric subgraphs;edge-labelings;Cartesian products;quotient graphs;
Podatki
Jezik: |
Angleški jezik |
Leto izida: |
2005 |
Tipologija: |
1.01 - Izvirni znanstveni članek |
Organizacija: |
UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko |
UDK: |
519.17 |
COBISS: |
13679193
|
ISSN: |
0364-9024 |
Št. ogledov: |
32 |
Št. prenosov: |
21 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Slovenski jezik |
Sekundarni naslov: |
Karakterizacija podgrafov Hammingovih grafov |
Sekundarni povzetek: |
Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph ▫$G$▫ is an induced subgraph of a Hamming graph if and only if there exist a labeling ▫$E(G)$▫ fulfilling the following two conditions: (i) incident edges receive the same label if and only if they lie on a common triangle; (ii) for any vertices ▫$u$▫ and ▫$v$▫ at distance at least two, there exist two labels such that they appear on any induced ▫$u,v$▫-path. |
Sekundarne ključne besede: |
Teorija grafov; |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Delo ni kategorizirano |
Strani: |
str. 302-312 |
Letnik: |
ǂVol. ǂ49 |
Zvezek: |
ǂno. ǂ4 |
Čas izdaje: |
2005 |
DOI: |
10.1002/jgt.20084 |
ID: |
1472511 |