Characterizing subgraphs of Hamming graphs

Klavžar, Sandi; Peterin, Iztok

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

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:	1169
Downloads:	81
Metadata:
Categories:	Misc.
:	KLAVŽAR, Sandi and PETERIN, Iztok, 2005, Characterizing subgraphs of Hamming graphs. Journal of graph theory [online]. 2005. Vol. 49, no. 4, p. 302–312. [Accessed 21 March 2025]. Retrieved from: http://www3.interscience.wiley.com/cgi-bin/jissue/110531259 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Journal of graph theory
Shortened title:	J. graph theory
Publisher:	J. Wiley & Sons
ISSN:	0364-9024
COBISS.SI-ID:	25747712

Secondary language

Language:	Slovenian
Title:	Karakterizacija podgrafov Hammingovih grafov
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$ .

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back