Loading [MathJax]/jax/output/HTML-CSS/jax.js
| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font
First page > Show document

Show document Help

Title:Tree-like isometric subgraphs of hypercubes
Authors:ID Brešar, Boštjan (Author)
ID Imrich, Wilfried (Author)
ID Klavžar, Sandi (Author)
Files:.pdf Discussiones_Mathematicae_Graph_Theory_2003_Bresar,_Imrich,_Klavzar_Tree-like_isometric_subgraphs_of_hypercubes.pdf (135,80 KB)
MD5: EA9AE3B5ECBCA8360FB1E524BAC7DB89
 
URL http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1199
 
Language:English
Work type:Unknown
Typology:1.01 - Original Scientific Article
Organization:FERI - Faculty of Electrical Engineering and Computer Science
Abstract:Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.
Keywords:mathematics, graph theory, Isometric embeddings, partial cubes, expansion procedures, trees, median graphs, graph automorphisms, automorphism groups, dismantlable graphs
Publication status:Published
Publication version:Version of Record
Year of publishing:2003
Number of pages:str. 227-240
Numbering:Letn. 23, št. 2
PID:20.500.12556/DKUM-65355 New window
ISSN:1234-3099
UDC:519.17
ISSN on article:1234-3099
COBISS.SI-ID:12621145 New window
NUK URN:URN:SI:UM:DK:MQ8H6RU7
Publication date in DKUM:31.03.2017
Views:1709
Downloads:393
Metadata:XML DC-XML DC-RDF
Categories:Misc.
:
BREŠAR, Boštjan, IMRICH, Wilfried and KLAVŽAR, Sandi, 2003, Tree-like isometric subgraphs of hypercubes. Discussiones mathematicae : Graph theory [online]. 2003. Vol. 23, no. 2, p. 227–240. [Accessed 21 March 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=65355
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:Bookmark and Share


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:Discussiones mathematicae : Graph theory
Shortened title:Discuss. Math., Graph Theory
Publisher:Technical University Press
ISSN:1234-3099
COBISS.SI-ID:7487065 New window

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:31.03.2017

Secondary language

Language:Slovenian
Title:Drevesom podobni izometrični podgrafi hiperkock
Abstract:Drevesom podobni podgrafi hiperkock predstavljajo posplošitev medianskih grafov. Tako kot medianski grafi podedujejo veliko lastnosti dreves, toda lahko vsebujejo večje razrede grafov, ki jih morda lahko hitreje prepoznamo kot medianske grafe. V članku proučujemo strukturo drevesom podobnih delnih kock, jih karakteriziramo in predstavimo primere podobnosti z drevesi in medianskimi grafi. Na primer, dokažemo, da so grafi kock drevesom podobnih delnih kock odstranljivi grafi. To med drugim implicira, da vsaka drevesom podobna delna kocka G vsebuje kocko, ki je invarianta za vse avtomorfizme G. Dokažemo tudi, da je vsaka šibka retrakcija takih grafov spet drevesom podobna delna kocka. Članek je zaključen z nekaj rezultati Fruchtovega tipa in s seznamov odprtih problemov.
Keywords:matematika, teorija grafov, izometrične vložitve, delne kocke, drevesa, ekspanzija, medianski grafi, avtomorfizmi grafov, grupe avtomorfizmov, odstranljivi grafi


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica