Currently displaying 1 – 20 of 51

Showing per page

Order by Relevance | Title | Year of publication

On graphs with a unique minimum hull set

Gary ChartrandPing Zhang — 2001

Discussiones Mathematicae Graph Theory

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.

The forcing geodetic number of a graph

Gary ChartrandPing Zhang — 1999

Discussiones Mathematicae Graph Theory

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...

The forcing convexity number of a graph

Gary ChartrandPing Zhang — 2001

Czechoslovak Mathematical Journal

For two vertices u and v of a connected graph G , the set I ( u , v ) consists of all those vertices lying on a u v geodesic in G . For a set S of vertices of G , the union of all sets I ( u , v ) for u , v S is denoted by I ( S ) . A set S is a convex set if I ( S ) = S . The convexity number c o n ( G ) of G is the maximum cardinality of a proper convex set of G . A convex set S in G with | S | = c o n ( G ) is called a maximum convex set. A subset T of a maximum convex set S of a connected graph G is called a forcing subset for S if S is the unique maximum convex set...

Extreme geodesic graphs

Gary ChartrandPing Zhang — 2002

Czechoslovak Mathematical Journal

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 of G , while for S V ( G ) , the set I [ S ] is the union of all sets I [ u , v ] for u , v S . A set S of vertices of G for which I [ S ] = V ( G ) is a geodetic set for G , and the minimum cardinality of a geodetic set is the geodetic number g ( G ) . A vertex v in G is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in G is its extreme order e x ( G ) . A graph G is an extreme geodesic...

H -convex graphs

Gary ChartrandPing Zhang — 2001

Mathematica Bohemica

For two vertices u and v in a connected graph G , the set I ( u , v ) consists of all those vertices lying on a u - v geodesic in G . For a set S of vertices of G , the union of all sets I ( u , v ) for u , v S is denoted by I ( S ) . A set S is convex if I ( S ) = S . The convexity number c o n ( G ) is the maximum cardinality of a proper convex set in G . A convex set S is maximum if | S | = c o n ( G ) . The cardinality of a maximum convex set in a graph G is the convexity number of G . For a nontrivial connected graph H , a connected graph G is an H -convex graph if G contains...

The forcing dimension of a graph

Gary ChartrandPing Zhang — 2001

Mathematica Bohemica

For an ordered set W = { w 1 , w 2 , , w k } of vertices and a vertex v in a connected graph G , the (metric) representation of v with respect to W is the k -vector r ( v | W ) = ( d ( v , w 1 ) , d ( v , w 2 ) , , d ( v , w k ) ), where d ( x , y ) represents the distance between the vertices x and y . The set W is a resolving set for G if distinct vertices of G have distinct representations. A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim ( G ) . For a basis W of G , a subset S of W is called a forcing subset of W if W is...

Geodetic sets in graphs

Gary ChartrandFrank HararyPing Zhang — 2000

Discussiones Mathematicae Graph Theory

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...

Distance defined by spanning trees in graphs

Gary ChartrandLadislav NebeskýPing Zhang — 2007

Discussiones Mathematicae Graph Theory

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...

Radio k-colorings of paths

Gary ChartrandLadislav NebeskýPing Zhang — 2004

Discussiones Mathematicae Graph Theory

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...

Page 1 Next

Download Results (CSV)