| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font
First page > Show document

Show document Help

Title:Arboreal structure and regular graphs of median-like classes
Authors:ID Brešar, Boštjan (Author)
Files:.pdf Discussiones_Mathematicae_Graph_Theory_2003_Bresar_Arboreal_structure_and_regular_graphs_of_median-like_classes.pdf (127,35 KB)
MD5: 90ED56DF748C8B8B97D4BD9C18DF3C11
 
URL http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1198
 
Language:English
Work type:Unknown
Typology:1.01 - Original Scientific Article
Organization:FERI - Faculty of Electrical Engineering and Computer Science
Abstract:We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which is a generalization of analogous procedure in median graphs. We characterize regular graphs of these classes whenever they enjoy an additional properties. As a corollary we derive that regular weakly median graphs are precisely Cartesian products in which each factor is a complete graph or a hyperoctahedron.
Keywords:mathematics, graph theory, median graph, tree, gatedness, amalgam, periphery, regular graph
Publication status:Published
Publication version:Version of Record
Year of publishing:2003
Number of pages:str. 215-225
Numbering:Letn. 23, št. 2
PID:20.500.12556/DKUM-65334 New window
ISSN:1234-3099
UDC:519.17
ISSN on article:1234-3099
COBISS.SI-ID:12602713 New window
NUK URN:URN:SI:UM:DK:TLVY6BWE
Publication date in DKUM:31.03.2017
Views:1070
Downloads:372
Metadata:XML DC-XML DC-RDF
Categories:Misc.
:
BREŠAR, Boštjan, 2003, Arboreal structure and regular graphs of median-like classes. Discussiones mathematicae : Graph theory [online]. 2003. Vol. 23, no. 2, p. 215–225. [Accessed 19 March 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=65334
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:Drevesna struktura in regularni grafi razredov grafov sorodnih medianskim grafom
Abstract:V članku so obravnavani razredi grafov, ki so zaprti za zastražene podgrafe, zastraženo amalgamacijo in kartezične produkte, ter zadoščajo še naslednji lastnosti: za vsak zastražen podgraf grafa tega razreda inverzna funkcija zastraženostne funkcije slika točke v zastražene podmnožice. Dokazano je, da vsak graf takega razreda vsebuje periferen podgraf, ki je kartezični produkt dveh grafov: zastraženega podgrafa danega grafa in pragrafa brez ene točke. Potemtakem za te grafe obstaja periferni eliminacijski postopek, ki je posplošitev analognega postopka na medianskih grafih. Podana je karakterizacija regularnih grafov teh razredov v primeru, ko razredi zadoščajo dodatni lastnosti. Posledično je izpeljano, da so regularni šibko medianski grafi natanko kartezični produkti, v katerih je vsak faktor bodisi poln graf bodisi hiperoktaeder.
Keywords:matematika, teorija grafov, medianski graf, drevo, zastraženost, amalgam, periferija, regularen graf


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