Povzetek
Koncept ▫$k$▫-Steinerjevih intervalov naravno posplošuje geodetske (binarne) intervale. Definiran je kot preslikava ▫$S: V\times \cdots \times V \longrightarrow 2^V$▫, kjer je ▫$S(u_1, \dots ,u_k)$▫ množica tistih vozlišč grafa ▫$G$▫, ki ležijo na kakem Steinerjevem drevesu glede na multimnožico ▫$W = \{u_1, \dots ,u_k\}$▫ vozlišč iz ▫$G$▫. V tem članku za vsako naravno število ▫$k$▫ dokažemo karakterizacijo razreda tistih grafov, v katerih imajo vsi ▫$k$▫-Steinerjevi intervali t.i. lastnost unije, ki pravi, da ▫$S(u_1,\ldots, u_k)$▫ sovpada z unijo geodetskih intervalov ▫$I(u_i,u_j)$▫ med vsemi pari vozlišč iz ▫$W$▫. Izkaže se, da tedaj, ko je ▫$k>3$▫, ta razred sovpada z razredom grafov, v katerih ▫$k$▫-Steinerjev interval zadošča aksiomu monotonosti(m), kot tudi z razredom grafov, v katerih ▫$k$▫-Steinerjev interval zadošča aksiomu (b2), ki sta pogoja iz teorije vmesnosti. In sicer preslikava ▫$S$▫ zadošča aksiomu (m), če iz ▫$x_1, \dots ,x_k \in S(u_1, \dots ,u_k)$▫ sledi ▫$S(x_1, \dots ,x_k) \subseteq S(u_1, \dots ,u_k)$▫; ter ▫$S$▫ zadošča (b2), če iz ▫$x \in S(u_1,u_2, \dots ,u_k)$▫ sledi ▫$S(x,u_2, \dots ,u_k) \subseteq S(u_1, \dots ,u_k)$▫. V primeru ▫$k=3$▫ so ti trije razredi grafov različni in za razreda grafov, v katerih Steinerjev interval zadošča lastnosti unije oz. aksiomu monotonosti (m), dokažemo strukturni karakterizaciji. Prav tako predstavimo več delnih ugotovitev za razred grafov, v katerih 3-Steinerjev interval zadošča aksimu (b2), ki vodijo do domneve, da so to natanko tisti grafi, v katerih je vsak blok geodetski graf z diametrom 2.
Ključne besede
matematika;teorija grafov;Steinerjev interval;geodetski interval;razdalja;vmesnost;monotonost;bločni graf;mathematics;graph theory;Steiner interval;geodesic interval;distance;betweenness;monotonicity;block graph;
Podatki
Jezik: |
Angleški jezik |
Leto izida: |
2009 |
Tipologija: |
1.01 - Izvirni znanstveni članek |
Organizacija: |
UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko |
UDK: |
519.17 |
COBISS: |
15334233
|
ISSN: |
0012-365X |
Št. ogledov: |
64 |
Št. prenosov: |
30 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Slovenski jezik |
Sekundarni naslov: |
Steinerjevi intervali, geodetski intervali in vmesnost |
Sekundarni povzetek: |
The concept of the ▫$k$▫-Steiner interval is a natural generalization of the geodesic (binary) interval. It is defined as a mapping ▫$S: V \times \cdots \times V \longrightarrow 2^V$▫ such that ▫$S(u_1,...,u_k)$▫ consists of all vertices in ▫$G$▫ that lie on some Steiner tree with respect to a multiset ▫$W =\{u_1,...,u_k\}$▫ of vertices from ▫$G$▫. In this paper we obtain, for each ▫$k$▫, a characterization of the class of graphs in which every ▫$k$▫-Steiner interval ▫$S$▫ has the so-called union property, which says that ▫$S(u_1,...,u_k)$▫ coincides with the union of geodesic intervals ▫$I(u_i,u_j)$▫ between all pairs from ▫$W$▫. It turns out that, as soon as ▫$k>3$▫, this class coincides with the class of graphs in which the ▫$k$▫-Steiner interval enjoys the monotone axiom (m), respectively (b2) axiom, the conditions from betweenness theory. Notably, ▫$S$▫ satisfies (m), if ▫$x_1,...,x_k \in S(u_1,...,u_k)$▫ implies ▫$S(x_1,...,x_k) \subseteq S(u_1,...,u_k)$▫, and ▫$S$▫ satisfies (b2) if ▫$x \in S(u_1,u_2,...,u_k)$▫ implies ▫$S(x,u_2,...,u_k) \subseteq S(u_1,...,u_k)$▫. In the case ▫$k=3$▫, these three classes are different, and we give structural characterizations of graphs for which their Steiner interval ▫$S$▫ satisfies the union property as well as the monotone axiom (m). We also prove several partial observations on the class ofgraphs in which the 3-Steiner interval satisfies (b2), which lead to the conjecture that these are precisely the graphs in which every block is a geodetic graph with diameter at most two. |
Sekundarne ključne besede: |
matematika;teorija grafov;Steinerjev interval;geodetski interval;razdalja;vmesnost;monotonost;bločni graf; |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Delo ni kategorizirano |
Strani: |
str. 6114-6125 |
Letnik: |
ǂVol. ǂ309 |
Zvezek: |
ǂiss. ǂ20 |
Čas izdaje: |
2009 |
ID: |
1474523 |