Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Modular and median signpost systems and their underlying graphs

100%

Mulder H., Nebeský L.

Discussiones Mathematicae Graph Theory

|

2003

|

tom 23

|

nr 2

309-324

EN

The concept of a signpost system on a set is introduced. It is a ternary relation on the set satisfying three fairly natural axioms. Its underlying graph is introduced. When the underlying graph is disconnected some unexpected things may happen. The main focus are signpost systems satisfying some extra axioms. Their underlying graphs have lots of structure: the components are modular graphs or median graphs. Yet another axiom guarantees that the underlying graph is also connected. The main results of this paper concern if-and-only-if characterizations involving signpost systems satisfying additional axioms on the one hand and modular, respectively median graphs on the other hand.

2

Leaps: an approach to the block structure of a graph

100%

Mulder H., Nebeský L.

Discussiones Mathematicae Graph Theory

|

2006

|

tom 26

|

nr 1

77-90

EN

To study the block structure of a connected graph G = (V,E), we introduce two algebraic approaches that reflect this structure: a binary operation + called a leap operation and a ternary relation L called a leap system, both on a finite, nonempty set V. These algebraic structures are easily studied by considering their underlying graphs, which turn out to be block graphs. Conversely, we define the operation $+_G$ as well as the set of leaps $L_G$ of the connected graph G. The underlying graph of $+_G$, as well as that of $L_G$, turns out to be just the block closure of G (i.e., the graph obtained by making each block of G into a complete subgraph).

3

Radio k-colorings of paths

81%

Chartrand G., Nebeský L., Zhang P.

Discussiones Mathematicae Graph Theory

|

2004

|

tom 24

|

nr 1

5-21

EN

For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings c of G. In this paper, radio k-colorings of paths are studied. For the path Pₙ of order n ≥ 9 and n odd, a new improved bound for $rc_{n- 2}(Pₙ)$ is presented. For n ≥ 4, it is shown that $rc_{n-3}(Pₙ) ≤ \binom{n-2} {2}$ Upper and lower bounds are also presented for rcₖ(Pₙ) in terms of k when 1 ≤ k ≤ n- 1. The upper bound is shown to be sharp when 1 ≤ k ≤ 4 and n is sufficiently large.

4

Distance defined by spanning trees in graphs

81%

Chartrand G., Nebeský L., Zhang P.

Discussiones Mathematicae Graph Theory

|

2007

|

tom 27

|

nr 3

485-506

EN

For a spanning tree T in a nontrivial connected graph G and for vertices u and v in G, there exists a unique u-v path u = u₀, u₁, u₂,..., uₖ = v in T. A u-v T-path in G is a u- v path u = v₀, v₁,...,vₗ = v in G that is a subsequence of the sequence u = u₀, u₁, u₂,..., uₖ = v. A u-v T-path of minimum length is a u-v T-geodesic in G. The T-distance $d_{G|T}(u,v)$ from u to v in G is the length of a u-v T-geodesic. Let geo(G) and geo(G|T) be the set of geodesics and the set of T-geodesics respectively in G. Necessary and sufficient conditions are established for (1) geo(G) = geo(G|T) and (2) geo(G|T) = geo(G|T*), where T and T* are two spanning trees of G. It is shown for a connected graph G that geo(G|T) = geo(G) for every spanning tree T of G if and only if G is a block graph. For a spanning tree T of a connected graph G, it is also shown that geo(G|T) satisfies seven of the eight axioms of the characterization of geo(G). Furthermore, we study the relationship between the distance d and T-distance $d_{G|T}$ in graphs and present several realization results on parameters and subgraphs defined by these two distances.

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

4 Nebeský L.

2 Chartrand G.

2 Mulder H.

2 Zhang P.

1 2007

1 2006

1 2004

1 2003

Modular and median signpost systems and their underlying graphs

Leaps: an approach to the block structure of a graph

Radio k-colorings of paths

Distance defined by spanning trees in graphs