20.500.12556/DKUM-51502 Characterizing subgraphs of Hamming graphs Karakterizacija podgrafov Hammingovih grafov 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. 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$▫. matematika teorija grafov Hammingovi grafi inducirani podgrafi izometrični podgrafi kartezični produkt grafov označevanje povezav kvocientni grafi mathematics graph theory Hamming graphs induced subgraphs isometric subgraphs edge-labelings Cartesian products quotient graphs true true false Angleški jezik Slovenski jezik Članek v reviji 2015-07-10 14:52:00 2015-07-10 14:52:00 2024-03-05 11:59:16 2019-07-11 07:20:46 2005 0 0 str. 302-312 no. 4 Vol. 49 2005 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 25747712 13679193 0364-9024 URN:SI:UM:DK:37BOGBXH http://www3.interscience.wiley.com/cgi-bin/jissue/110531259 1 https://dk.um.si/Dokument.php?lang=slv&id=76062 Pedagoška fakulteta 0 0 0