Median and quasi-median direct products of graphs
Povzetek
Karakterizirani so tisti medianski grafi, ki so direktni produkt grafov z vsaj tremi točkami. Poleg nekaj pogostih primerov je dokazano, da je komponenta grafa ▫$G \times K_3$▫ medianska natanko tedaj, ko je ▫$G$▫ drevo, v katerem je razdalja med poljubnima točkama stopnje vsaj tri sodo število. Dokazanih je tudi nekaj delnih rezultatov o medianskih grafih oblike ▫$G \times K_2$▫. Nazadnje je dokazano, da je ▫$K_3 \times K_3$▫ edini nedvodelni kvazimedianski direktni produkt.
Ključne besede
matematika;teorija grafov;medianski graf;direktni produkt;kvazimedianski graf;izometrične vložitve;konveksnost;mathematics;graph theory;median graph;direct product;quasi-median graph;isometric embeddings;convexity;
Podatki
| Jezik: | Angleški jezik |
|---|---|
| Leto izida: | 2005 |
| Tipologija: | 1.01 - Izvirni znanstveni članek |
| Organizacija: | UM FS - Fakulteta za strojništvo |
| UDK: | 519.17 |
| COBISS: |
13477721
|
| ISSN: | 1234-3099 |
| Št. ogledov: | 716 |
| Št. prenosov: | 282 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Slovenski jezik |
|---|---|
| Sekundarni naslov: | Medianski in kvazimedianski direktni produkti grafov |
| Sekundarni povzetek: | Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of ▫$G \times P_3$▫ is median if and only if ▫$G$▫ is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form ▫$G \times K_2▫$ are proved, and it is shown that the only nonbipartite quasi-median direct product is ▫$K_3 \times K_3$▫. |
| Sekundarne ključne besede: | matematika;teorija grafov;medianski graf;direktni produkt;kvazimedianski graf;izometrične vložitve;konveksnost; |
| URN: | URN:SI:UM: |
| Vrsta dela (COBISS): | Znanstveno delo |
| Strani: | str. 183-196 |
| Letnik: | ǂVol. ǂ25 |
| Zvezek: | ǂno. ǂ1-2 |
| Čas izdaje: | 2005 |
| ID: | 9595936 |
Priporočena dela:
Median and quasi-median direct products of graphs
2005,
ni podatka o podnaslovu
On cube-free median graphs
2007,
ni podatka o podnaslovu
On cube-free median graphs
2003,
ni podatka o podnaslovu
Characterizing almost-median graphs
2007,
ni podatka o podnaslovu
A characterization of the edge connectivity of direct products of graphs
2013,
ni podatka o podnaslovu