Cube intersection concepts in median graphs

Brešar, Boštjan; Kraner Šumenjak, Tadeja

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Cube intersection concepts in median graphs
Authors:	ID Brešar, Boštjan (Author) ID Kraner Šumenjak, Tadeja (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2008.07.032
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
Abstract:	Obravnavamo različne razrede presečnih grafov maksimalnih hiperkock medianskih grafov. Za medianski graf $G$ in celo število $k ge 0$ je presečni graf ${mathcal{Q}}_k(G)$ definiran kot tisti graf, katerega vozlišča so maksimalne hiperkocke (z ozirom na inkluzijo) grafa $G$ in sta dve vozlišči $H_x$ in $H_y$ v njem sosednji tedaj, ko presek $H_x cap H_y$ vsebuje podgraf izomorfen $Q_k$ . V članku predstavimo karakterizacije kličnih grafov z uporabo omenjenih presečnih konceptov, ko je $k>0$ . Vpeljemo tudi t.i. maksimalno 2-presečni graf maksimalnih hiperkock medianskega grafa $G$ , ki ga označimo z ${mathcal{Q}}_{m2}(G)$ in predstavlja tisti graf, katerega vozlišča somaksimalne hiperkocke grafa $G$ , dve vozlišči v njem pa sta sosednji, če presek pripadajočih hiperkock ni strogo vsebovan v kakem preseku dveh maksimalnih hiperkock. Dokažemo, da je graf $H$ brez induciranih diamantov, če in samo če obstaja takšen medianski graf $G$ , da je $H$ izomorfen ${mathcal{Q}}_{m2}(G)$ . Obravnavamo tudi konvergenco medianskega grafa h grafu na enem vozlišču glede na vse vpeljane operacije.
Keywords:	matematika, teorija grafov, kartezični produkt, medianski graf, graf kock, presečni graf, konveksnost, mathematics, graph theory, Cartesian product, median graph, cube graph, intersection graph, convexity
Year of publishing:	2009
Number of pages:	str. 2990-2997
Numbering:	Vol. 309, iss. 10
PID:	20.500.12556/DKUM-51791
UDC:	519.17
ISSN on article:	0012-365X
COBISS.SI-ID:	15167065
NUK URN:	URN:SI:UM:DK:XIOAADIY
Publication date in DKUM:	10.07.2015
Views:	1369
Downloads:	106
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan and KRANER ŠUMENJAK, Tadeja, 2009, Cube intersection concepts in median graphs. Discrete mathematics [online]. 2009. Vol. 309, no. 10, p. 2990–2997. [Accessed 9 April 2025]. Retrieved from: http://dx.doi.org/10.1016/j.disc.2008.07.032 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:

Tranzitivni, lokalno končni medianski grafi s končnimi bloki
Mulder, Henry Martin: Metric graph theory: the case of median graphs. - Graph connections (Cochin, 1998), 19-32, Allied Publ., New Delhi, 1999
Brešar, Boštjan: On the natural imprint function of a graph. - European J. Combin. 23 (2002), no. 2, 149-161
Križni grafi grafov zastraženih inverzov
Relations between median graphs, semi-median graphs and partial cubes

Similar works from other repositories:

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:	Discrete mathematics
Shortened title:	Discrete math.
Publisher:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

Secondary language

Language:	Unknown
Title:	Presečni koncepti kock v medianskih grafih
Abstract:	We study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph $G$ and $k ge 0$ , the intersection graph ${mathcal{Q}}_k(G)$ is defined as the graph whose vertices are maximal hypercubes (by inclusion) in $G$ , and two vertices $H_x$ and $H_y$ in ${mathcal{Q}}_k(G)$ are adjacent whenever the intersection $H_x cap H_y$ contains a subgraph isomorphic to $Q_k$ . Characterizations of clique-graphs in terms of these intersection concepts when $k>0$ , are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph $G$ , denoted ${mathcal{Q}}_{m2}(G)$ whose vertices are maximal hypercubes of $G$ , and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph $H$ is diamond-free if and only if there exists a median graph $G$ such that $H$ is isomorphic to ${mathcal{Q}}_{m2}(G)$ . We also study convergence of median graphs to the one-vertex graph with respect to all these operations.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back