Median and quasi-median direct products of graphs
Abstract
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.
Keywords
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;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2005 |
| Typology: | 1.01 - Original Scientific Article |
| Organization: | UM FS - Faculty of Mechanical Engineering |
| UDC: | 519.17 |
| COBISS: |
13477721
|
| ISSN: | 1234-3099 |
| Views: | 716 |
| Downloads: | 282 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | Slovenian |
|---|---|
| Secondary title: | Medianski in kvazimedianski direktni produkti grafov |
| Secondary abstract: | 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$▫. |
| Secondary keywords: | matematika;teorija grafov;medianski graf;direktni produkt;kvazimedianski graf;izometrične vložitve;konveksnost; |
| URN: | URN:SI:UM: |
| Type (COBISS): | Scientific work |
| Pages: | str. 183-196 |
| Volume: | ǂVol. ǂ25 |
| Issue: | ǂno. ǂ1-2 |
| Chronology: | 2005 |
| ID: | 9595936 |
Recommended works:
Median and quasi-median direct products of graphs
2005,
no subtitle data available
On cube-free median graphs
2007,
no subtitle data available
On cube-free median graphs
2003,
no subtitle data available
Characterizing almost-median graphs
2007,
no subtitle data available
A characterization of the edge connectivity of direct products of graphs
2013,
no subtitle data available