Janja Jerebic (Author), Sandi Klavžar (Author)

Abstract

Krepka izometrična dimenzija ▫$\textrm{idim}(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$k$▫, za katero lahko ▫$G$▫ izometrično vložimo v krepki produkt ▫$k$▫ poti. Problem določitve ▫$\textrm{idim}(G)$▫ za grafe premera dva je reduciran na problem pokrivanja komplementa grafa ▫$G$▫ s polnimi dvodelnimi grafi. Za primer je pokazano, da je izometrična dimenzija Petersenovega grafa enaka 5.

Keywords

matematika;teorija grafov;izometrični podgraf;krepki produkt grafov;premer grafa;krepka izometrična dimenzija;Petersenov graf;mathematics;graph theory;isometric subgraph;strong product of graphs;graph diameter;strong isometric dimension;Petersen graph;

Data

Language: English
Year of publishing:
Typology: 0 - Not set
Organization: UM PEF - Faculty of Education
UDC: 519.17
COBISS: 12396377 Link will open in a new window
ISSN: 1318-4865
Views: 42
Downloads: 10
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: Slovenian
Secondary title: Krepka izometrična dimenzija grafov premera dva
Secondary abstract: The strong isometric dimension ▫$\textrm{idim}(G)$▫ of a graph ▫$G$▫ is the least number ▫$k$▫ such that ▫$G$▫ can be isometrically embedded into the strong product of ▫$k$▫ paths. The problem of determining ▫$\textrm{idim}(G)$▫ for graphs of diameter two is reduced to a covering problem of the complement of ▫$G$▫ with complete bipartite graphs. As an example it is shown that ▫$\textrm{idim}(P) = 5$▫, where ▫$P$▫ is the Petersen graph.
Secondary keywords: matematika;teorija grafov;izometrični podgraf;krepki produkt grafov;premer grafa;krepka izometrična dimenzija;Petersenov graf;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 1-8
Volume: ǂVol. ǂ41
Issue: ǂšt. ǂ876
Chronology: 2003
ID: 66335