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

Abstract

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$▫.

Keywords

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;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FERI - Faculty of Electrical Engineering and Computer Science
UDC: 519.17
COBISS: 13679193 Link will open in a new window
ISSN: 0364-9024
Views: 32
Downloads: 21
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary title: Karakterizacija podgrafov Hammingovih grafov
Secondary abstract: 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.
Secondary keywords: Teorija grafov;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 302-312
Volume: ǂVol. ǂ49
Issue: ǂno. ǂ4
Chronology: 2005
DOI: 10.1002/jgt.20084
ID: 1472511