| Title: | Characterizing subgraphs of Hamming graphs |
|---|
| Authors: | ID Klavžar, Sandi (Author)
ID Peterin, Iztok (Author) |
|---|
| Files: |  http://www3.interscience.wiley.com/cgi-bin/jissue/110531259
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | PEF - Faculty of Education
|
|---|
| 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.
|
|---|
| Keywords: | 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 |
|---|
| Year of publishing: | 2005 |
|---|
| Number of pages: | str. 302-312 |
|---|
| Numbering: | Vol. 49, no. 4 |
|---|
| PID: | 20.500.12556/DKUM-51502  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0364-9024 |
|---|
| COBISS.SI-ID: | 13679193 |
|---|
| NUK URN: | URN:SI:UM:DK:37BOGBXH |
|---|
| Publication date in DKUM: | 10.07.2015 |
|---|
| Views: | 1347 |
|---|
| Downloads: | 85 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
