Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 10

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  geodetic number
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Geodetic sets in graphs

100%
Chartrand G., Harary F., Zhang P.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 1
129-138
EN
For two vertices u and v of a graph G, the closed interval I[u,v] consists of u, v, and all vertices lying in some u-v geodesic in G. If S is a set of vertices of G, then I[S] is the union of all sets I[u,v] for u, v ∈ S. If I[S] = V(G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for every two distinct vertices u,v ∈ S, there exists a third vertex w of G that lies in some u-v geodesic but in no x-y geodesic for x, y ∈ S and {x,y} ≠ {u,v}. It is shown that for every integer k ≥ 2, there exists a connected graph G with g(G) = k which contains a uniform, essential minimum geodetic set. A minimal geodetic set S has no proper subset which is a geodetic set. The maximum cardinality of a minimal geodetic set is the upper geodetic number g⁺(G). It is shown that every two integers a and b with 2 ≤ a ≤ b are realizable as the geodetic and upper geodetic numbers, respectively, of some graph and when a < b the minimum order of such a graph is b+2.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The forcing geodetic number of a graph

100%
Chartrand G., Zhang P.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 1
45-58
EN
For two vertices u and v of a graph G, the set I(u, v) consists of all vertices lying on some u-v geodesic in G. If S is a set of vertices of G, then I(S) is the union of all sets I(u,v) for u, v ∈ S. A set S is a geodetic set if I(S) = V(G). A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number g(G). A subset T of a minimum geodetic set S is called a forcing subset for S if S is the unique minimum geodetic set containing T. The forcing geodetic number $f_G(S)$ of S is the minimum cardinality among the forcing subsets of S, and the forcing geodetic number f(G) of G is the minimum forcing geodetic number among all minimum geodetic sets of G. The forcing geodetic numbers of several classes of graphs are determined. For every graph G, f(G) ≤ g(G). It is shown that for all integers a, b with 0 ≤ a ≤ b, a connected graph G such that f(G) = a and g(G) = b exists if and only if (a,b) ∉ {(1,1),(2,2)}.
3
Content available remote

Products of Geodesic Graphs and the Geodetic Number of Products

100%
Soloff J. A., Márquez R. A., Friedler L. M.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
35-42
EN
Given a connected graph and a vertex x ∈ V (G), the geodesic graph Px(G) has the same vertex set as G with edges uv iff either v is on an x − u geodesic path or u is on an x − v geodesic path. A characterization is given of those graphs all of whose geodesic graphs are complete bipartite. It is also shown that the geodetic number of the Cartesian product of Km,n with itself, where m, n ≥ 4, is equal to the minimum of m, n and eight.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The hull number of strong product graphs

100%
Santhakumaran A., Ullas Chandran S.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
493-507
EN
For a connected graph G with at least two vertices and S a subset of vertices, the convex hull $[S]_G$ is the smallest convex set containing S. The hull number h(G) is the minimum cardinality among the subsets S of V(G) with $[S]_G = V(G)$. Upper bound for the hull number of strong product G ⊠ H of two graphs G and H is obtainted. Improved upper bounds are obtained for some class of strong product graphs. Exact values for the hull number of some special classes of strong product graphs are obtained. Graphs G and H for which h(G⊠ H) = h(G)h(H) are characterized.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Double geodetic number of a graph

100%
Santhakumaran A., Jebaraj T.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 1
109-119
EN
For a connected graph G of order n, a set S of vertices is called a double geodetic set of G if for each pair of vertices x,y in G there exist vertices u,v ∈ S such that x,y ∈ I[u,v]. The double geodetic number dg(G) is the minimum cardinality of a double geodetic set. Any double godetic of cardinality dg(G) is called dg-set of G. The double geodetic numbers of certain standard graphs are obtained. It is shown that for positive integers r,d such that r < d ≤ 2r and 3 ≤ a ≤ b there exists a connected graph G with rad G = r, diam G = d, g(G) = a and dg(G) = b. Also, it is proved that for integers n, d ≥ 2 and l such that 3 ≤ k ≤ l ≤ n and n-d-l+1 ≥ 0, there exists a graph G of order n diameter d, g(G) = k and dg(G) = l.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the forcing geodetic and forcing steiner numbers of a graph

100%
Santhakumaran A., John J.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
611-624
EN
For a connected graph G = (V,E), a set W ⊆ V is called a Steiner set of G if every vertex of G is contained in a Steiner W-tree of G. The Steiner number s(G) of G is the minimum cardinality of its Steiner sets and any Steiner set of cardinality s(G) is a minimum Steiner set of G. For a minimum Steiner set W of G, a subset T ⊆ W is called a forcing subset for W if W is the unique minimum Steiner set containing T. A forcing subset for W of minimum cardinality is a minimum forcing subset of W. The forcing Steiner number of W, denoted by fₛ(W), is the cardinality of a minimum forcing subset of W. The forcing Steiner number of G, denoted by fₛ(G), is fₛ(G) = min{fₛ(W)}, where the minimum is taken over all minimum Steiner sets W in G. The geodetic number g(G) and the forcing geodetic number f(G) of a graph G are defined in [2]. It is proved in [6] that there is no relationship between the geodetic number and the Steiner number of a graph so that there is no relationship between the forcing geodetic number and the forcing Steiner number of a graph. We give realization results for various possibilities of these four parameters.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The forcing steiner number of a graph

100%
Santhakumaran A., John J.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
171-181
EN
For a connected graph G = (V,E), a set W ⊆ V is called a Steiner set of G if every vertex of G is contained in a Steiner W-tree of G. The Steiner number s(G) of G is the minimum cardinality of its Steiner sets and any Steiner set of cardinality s(G) is a minimum Steiner set of G. For a minimum Steiner set W of G, a subset T ⊆ W is called a forcing subset for W if W is the unique minimum Steiner set containing T. A forcing subset for W of minimum cardinality is a minimum forcing subset of W. The forcing Steiner number of W, denoted by fₛ(W), is the cardinality of a minimum forcing subset of W. The forcing Steiner number of G, denoted by fₛ(G), is fₛ(G) = min{fₛ(W)}, where the minimum is taken over all minimum Steiner sets W in G. Some general properties satisfied by this concept are studied. The forcing Steiner numbers of certain classes of graphs are determined. It is shown for every pair a, b of integers with 0 ≤ a < b, b ≥ 2, there exists a connected graph G such that fₛ(G) = a and s(G) = b.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The geodetic number of strong product graphs

88%
Santhakumaran A., Ullas Chandran S.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
687-700
EN
For two vertices u and v of a connected graph G, the set $I_G[u,v]$ consists of all those vertices lying on u-v geodesics in G. Given a set S of vertices of G, the union of all sets $I_G[u,v]$ for u,v ∈ S is denoted by $I_G[S]$. A set S ⊆ V(G) is a geodetic set if $I_G[S] = V(G)$ and the minimum cardinality of a geodetic set is its geodetic number g(G) of G. Bounds for the geodetic number of strong product graphs are obtainted and for several classes improved bounds and exact values are obtained.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On graphs with a unique minimum hull set

75%
Chartrand G., Zhang P.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
31-42
EN
We show that for every integer k ≥ 2 and every k graphs G₁,G₂,...,Gₖ, there exists a hull graph with k hull vertices v₁,v₂,...,vₖ such that link $L(v_i) = G_i$ for 1 ≤ i ≤ k. Moreover, every pair a, b of integers with 2 ≤ a ≤ b is realizable as the hull number and geodetic number (or upper geodetic number) of a hull graph. We also show that every pair a,b of integers with a ≥ 2 and b ≥ 0 is realizable as the hull number and forcing geodetic number of a hull graph.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The edge geodetic number and Cartesian product of graphs

75%
Santhakumaran A., Ullas Chandran S.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 1
55-73
EN
For a nontrivial connected graph G = (V(G),E(G)), a set S⊆ V(G) is called an edge geodetic set of G if every edge of G is contained in a geodesic joining some pair of vertices in S. The edge geodetic number g₁(G) of G is the minimum order of its edge geodetic sets. Bounds for the edge geodetic number of Cartesian product graphs are proved and improved upper bounds are determined for a special class of graphs. Exact values of the edge geodetic number of Cartesian product are obtained for several classes of graphs. Also we obtain a necessary condition of G for which g₁(G ☐ K₂) = g₁(G).
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.