Sandi Klavžar (Avtor), Iztok Peterin (Avtor)

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:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK: 519.17
COBISS: 13679193 Povezava se bo odprla v novem oknu
ISSN: 0364-9024
Št. ogledov: 32
Št. prenosov: 21
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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