Cube intersection concepts in median graphs

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

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Cube intersection concepts in median graphs
Avtorji:	ID Brešar, Boštjan (Avtor) ID Kraner Šumenjak, Tadeja (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.disc.2008.07.032
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Opis:	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.
Ključne besede:	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
Leto izida:	2009
Št. strani:	str. 2990-2997
Številčenje:	Vol. 309, iss. 10
PID:	20.500.12556/DKUM-51791
UDK:	519.17
COBISS.SI-ID:	15167065
ISSN pri članku:	0012-365X
NUK URN:	URN:SI:UM:DK:XIOAADIY
Datum objave v DKUM:	10.07.2015
Število ogledov:	1369
Število prenosov:	106
Metapodatki:
Področja:	Ostalo
:	BREŠAR, Boštjan in KRANER ŠUMENJAK, Tadeja, 2009, Cube intersection concepts in median graphs. Discrete mathematics [na spletu]. 2009. Vol. 309, no. 10, p. 2990–2997. [Dostopano 9 april 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.disc.2008.07.032 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Podobna dela iz repozitorija:

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

Podobna dela iz ostalih repozitorijev:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	Discrete mathematics
Skrajšan naslov:	Discrete math.
Založnik:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

Sekundarni jezik

Jezik:	Neznan jezik
Naslov:	Presečni koncepti kock v medianskih grafih
Opis:	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.

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj