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;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FKBV - Faculty of Agriculture
UDC: 519.17
COBISS: 15167065 Link will open in a new window
ISSN: 0012-365X
Views: 775
Downloads: 92
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Unknown
Secondary title: Presečni koncepti kock v medianskih grafih
Secondary 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.
Secondary keywords: matematika;teorija grafov;kartezični produkt;medianski graf;graf kock;presečni graf;konveksnost;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 2990-2997
Volume: ǂVol. ǂ309
Issue: ǂiss. ǂ10
Chronology: 2009
ID: 1474305
Recommended works:
, no subtitle data available
, no subtitle data available
, no subtitle data available
, no subtitle data available
, no subtitle data available