Currently displaying 1 – 11 of 11

Showing per page

Order by Relevance | Title | Year of publication

Connected partition dimensions of graphs

Varaporn SaenpholphatPing Zhang — 2002

Discussiones Mathematicae Graph Theory

For a vertex v of a connected graph G and a subset S of V(G), the distance between v and S is d(v,S) = mind(v,x)|x ∈ S. For an ordered k-partition Π = S₁,S₂,...,Sₖ of V(G), the representation of v with respect to Π is the k-vector r(v|Π) = (d(v,S₁), d(v,S₂),..., d(v,Sₖ)). The k-partition Π is a resolving partition if the k-vectors r(v|Π), v ∈ V(G), are distinct. The minimum k for which there is a resolving k-partition of V(G) is the partition dimension pd(G) of G. A resolving partition Π = S₁,S₂,...,Sₖ...

On connected resolving decompositions in graphs

Varaporn SaenpholphatPing Zhang — 2004

Czechoslovak Mathematical Journal

For an ordered k -decomposition 𝒟 = { G 1 , G 2 , , G k } of a connected graph G and an edge e of G , the 𝒟 -code of e is the k -tuple c 𝒟 ( e ) = ( d ( e , G 1 ) , d ( e , G 2 ) , ... , d ( e , G k ) ) , where d ( e , G i ) is the distance from e to G i . A decomposition 𝒟 is resolving if every two distinct edges of G have distinct 𝒟 -codes. The minimum k for which G has a resolving k -decomposition is its decomposition dimension dim d ( G ) . A resolving decomposition 𝒟 of G is connected if each G i is connected for 1 i k . The minimum k for which G has a connected resolving k -decomposition is its connected decomposition...

Connected resolvability of graphs

Varaporn SaenpholphatPing Zhang — 2003

Czechoslovak Mathematical Journal

For an ordered set W = { w 1 , w 2 , , w k } of vertices and a vertex v in a connected graph G , the 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 with respect to W . A resolving set for G containing a minimum number of vertices is a basis for G . The dimension dim ( G ) is the number of vertices in a basis for G . A resolving set W of G is connected if the subgraph...

Connected resolving decompositions in graphs

Varaporn SaenpholphatPing Zhang — 2003

Mathematica Bohemica

For an ordered k -decomposition 𝒟 = { G 1 , G 2 , ... , G k } of a connected graph G and an edge e of G , the 𝒟 -code of e is the k -tuple c 𝒟 ( e ) = ( d ( e , G 1 ) , d ( e , G 2 ) , ... , d ( e , G k ) ), where d ( e , G i ) is the distance from e to G i . A decomposition 𝒟 is resolving if every two distinct edges of G have distinct 𝒟 -codes. The minimum k for which G has a resolving k -decomposition is its decomposition dimension dim d ( G ) . A resolving decomposition 𝒟 of G is connected if each G i is connected for 1 i k . The minimum k for which G has a connected...

The upper traceable number of a graph

Futaba OkamotoPing ZhangVaraporn Saenpholphat — 2008

Czechoslovak Mathematical Journal

For a nontrivial connected graph G of order n and a linear ordering s v 1 , v 2 , ... , v n of vertices of G , define d ( s ) = i = 1 n - 1 d ( v i , v i + 1 ) . The traceable number t ( G ) of a graph G is t ( G ) = min { d ( s ) } and the upper traceable number t + ( G ) of G is t + ( G ) = max { d ( s ) } , where the minimum and maximum are taken over all linear orderings s of vertices of G . We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t + ( G ) - t ( G ) = 1 are characterized and a formula for the upper...

Measures of traceability in graphs

Varaporn SaenpholphatFutaba OkamotoPing Zhang — 2006

Mathematica Bohemica

For a connected graph G of order n 3 and an ordering s v 1 , v 2 , , v n of the vertices of G , d ( s ) = i = 1 n - 1 d ( v i , v i + 1 ) , where d ( v i , v i + 1 ) is the distance between v i and v i + 1 . The traceable number t ( G ) of G is defined by t ( G ) = min d ( s ) , where the minimum is taken over all sequences s of the elements of V ( G ) . It is shown that if G is a nontrivial connected graph of order n such that l is the length of a longest path in G and p is the maximum size of a spanning linear forest in G , then 2 n - 2 - p t ( G ) 2 n - 2 - l and both these bounds are sharp. We establish a formula for the traceable number of...

The independent resolving number of a graph

Gary ChartrandVaraporn SaenpholphatPing Zhang — 2003

Mathematica Bohemica

For an ordered set W = { w 1 , w 2 , , w k } of vertices in a connected graph G and a vertex v of G , the code of v with respect to W is the k -vector c W ( v ) = ( d ( v , w 1 ) , d ( v , w 2 ) , , d ( v , w k ) ) . The set W is an independent resolving set for G if (1) W is independent in G and (2) distinct vertices have distinct codes with respect to W . The cardinality of a minimum independent resolving set in G is the independent resolving number i r ( G ) . We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs G of order n with i r ( G ) = 1 , n - 1 ,...

On γ -labelings of oriented graphs

Futaba OkamotoPing ZhangVaraporn Saenpholphat — 2007

Mathematica Bohemica

Let D be an oriented graph of order n and size m . A γ -labeling of D is a one-to-one function f V ( D ) { 0 , 1 , 2 , ... , m } that induces a labeling f ' E ( D ) { ± 1 , ± 2 , ... , ± m } of the arcs of D defined by f ' ( e ) = f ( v ) - f ( u ) for each arc e = ( u , v ) of D . The value of a γ -labeling f is v a l ( f ) = e E ( G ) f ' ( e ) . A γ -labeling of D is balanced if the value of f is 0. An oriented graph D is balanced if D has a balanced labeling. A graph G is orientably balanced if G has a balanced orientation. It is shown that a connected graph G of order n 2 is orientably balanced unless G is a tree, n 2 ( m o d 4 ) , and every vertex of...

Page 1

Download Results (CSV)