A set <em>S ⊆ V (G)</em> is called a geodetic set if every vertex of <em>G</em> lies on a shortest <em>u-v</em> path for some <em>u, v ∈ S</em>, the minimum cardinality...A set <em>S ⊆ V (G)</em> is called a geodetic set if every vertex of <em>G</em> lies on a shortest <em>u-v</em> path for some <em>u, v ∈ S</em>, the minimum cardinality among all geodetic sets is called geodetic number and is denoted by <img src="Edit_82259359-0135-4a65-9378-b767f0405b48.png" alt="" />. A set <em>C ⊆ V (G)</em> is called a chromatic set if <em>C</em> contains all vertices of different colors in<em> G</em>, the minimum cardinality among all chromatic sets is called the chromatic number and is denoted by <img src="Edit_d849148d-5778-459b-abbb-ff25b5cd659b.png" alt="" />. A geo-chromatic set<em> S</em><sub><em>c</em></sub><em> ⊆ V (G</em><em>)</em> is both a geodetic set and a chromatic set. The geo-chromatic number <img src="Edit_505e203c-888c-471c-852d-4b9c2dd1a31c.png" alt="" /><em> </em>of<em> G</em> is the minimum cardinality among all geo-chromatic sets of<em> G</em>. In this paper, we determine the geodetic number and the geo-chromatic number of 2-cartesian product of some standard graphs like complete graphs, cycles and paths.展开更多
For every two vertices u and v in a graph G, a u-v geodesic is a shortest path between u and v. Let I(u, v) denote the set of all vertices lying on a u-v geodesic. For a vertex subset S, let I(S) denote the union of a...For every two vertices u and v in a graph G, a u-v geodesic is a shortest path between u and v. Let I(u, v) denote the set of all vertices lying on a u-v geodesic. For a vertex subset S, let I(S) denote the union of all I(u, v) for u, v ∈ S. The geodetic number g(G) of a graph G is the minimum cardinality of a set S with I(S) = V (G). For a digraph D, there is analogous terminology for the geodetic number g(D). The geodetic spectrum of a graph G, denoted by S(G), is the set of geodetic numbers of all orientations of graph G. The lower geodetic number is g ?(G) = minS(G) and the upper geodetic number is g +(G) = maxS(G). The main purpose of this paper is to study the relations among g(G), g ?(G) and g +(G) for connected graphs G. In addition, a sufficient and necessary condition for the equality of g(G) and g(G × K 2) is presented, which improves a result of Chartrand, Harary and Zhang.展开更多
文摘A set <em>S ⊆ V (G)</em> is called a geodetic set if every vertex of <em>G</em> lies on a shortest <em>u-v</em> path for some <em>u, v ∈ S</em>, the minimum cardinality among all geodetic sets is called geodetic number and is denoted by <img src="Edit_82259359-0135-4a65-9378-b767f0405b48.png" alt="" />. A set <em>C ⊆ V (G)</em> is called a chromatic set if <em>C</em> contains all vertices of different colors in<em> G</em>, the minimum cardinality among all chromatic sets is called the chromatic number and is denoted by <img src="Edit_d849148d-5778-459b-abbb-ff25b5cd659b.png" alt="" />. A geo-chromatic set<em> S</em><sub><em>c</em></sub><em> ⊆ V (G</em><em>)</em> is both a geodetic set and a chromatic set. The geo-chromatic number <img src="Edit_505e203c-888c-471c-852d-4b9c2dd1a31c.png" alt="" /><em> </em>of<em> G</em> is the minimum cardinality among all geo-chromatic sets of<em> G</em>. In this paper, we determine the geodetic number and the geo-chromatic number of 2-cartesian product of some standard graphs like complete graphs, cycles and paths.
基金the National Natural Science Foundation of China(Grant Nos.10301010,60673048)the Science and Technology Commission of Shanghai Municipality(Grant No.04JC14031)
文摘For every two vertices u and v in a graph G, a u-v geodesic is a shortest path between u and v. Let I(u, v) denote the set of all vertices lying on a u-v geodesic. For a vertex subset S, let I(S) denote the union of all I(u, v) for u, v ∈ S. The geodetic number g(G) of a graph G is the minimum cardinality of a set S with I(S) = V (G). For a digraph D, there is analogous terminology for the geodetic number g(D). The geodetic spectrum of a graph G, denoted by S(G), is the set of geodetic numbers of all orientations of graph G. The lower geodetic number is g ?(G) = minS(G) and the upper geodetic number is g +(G) = maxS(G). The main purpose of this paper is to study the relations among g(G), g ?(G) and g +(G) for connected graphs G. In addition, a sufficient and necessary condition for the equality of g(G) and g(G × K 2) is presented, which improves a result of Chartrand, Harary and Zhang.
