Search

In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a Π- contractible directed cycle of G, then both of Int( C,Π) and Ext( C,Π) are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface S with f( G) ≥ 2 ( f( G) is the face-width of G), then any cycle base of G must contain at least 2 g noncontractible directed cycles; if G has been embedded in non-orientable surface N, then any cycle base of G must contain at least g noncontractible directed cycles. [ABSTRACT FROM AUTHOR]

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, υ ∈ V ( G) there is a vertex w ∈ W such that d( u,w) ≠ d( υ,w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim( G). For a vertex u of G and a subset S of V ( G), the distance between u and S is the number min d( u, s). A k-partition Π = { S, S, ..., S} of V ( G) is called a resolving partition if for every two distinct vertices u, v ∈ V ( G) there is a set S in Π such that d( u, S) ≠ d( v, S). The minimum k for which there is a resolving k-partition of V ( G) is called the partition dimension of G, denoted by pd( G). The circulant graph is a graph with vertex set ℤ, an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i − j (mod n) ∈ C, where C ∈ ℤ has the property that C = −C and 0 ∉ C. The circulant graph is denoted by X where Δ = | C|. In this paper, we study the metric dimension of a family of circulant graphs X with connection set $$C = \left\{ {1,\tfrac{n} {2},n - 1} \right\}$$ and prove that dim( X) is independent of choice of n by showing that We also study the partition dimension of a family of circulant graphs X with connection set C = {±1,±2} and prove that pd( X) is independent of choice of n and show that pd( X) = 5 and . [ABSTRACT FROM AUTHOR]

The domination number Γ( G) of a connected graph G of order n is bounded below by $$\tfrac{{n + 2 - \varepsilon (G)}} {3}$$, where ε( G) denotes the maximum number of leaves in any spanning tree of G. We show that $$\tfrac{{n + 2 - \varepsilon (G)}} {3} = \gamma (G)$$ if and only if there exists a tree $$T \in \mathcal{T}(G) \cap \mathcal{R}$$ such that n( T) = ε( G), where n( T) denotes the number of leaves of T, $$\mathcal{R}$$ denotes the family of all trees in which the distance between any two distinct leaves is congruent to 2 modulo 3, and $$\mathcal{T}$$ ( G) denotes the set composed by the spanning trees of G. As a consequence of the study, we show that if $$\tfrac{{n + 2 - \varepsilon (G)}} {3} = \gamma (G)$$, then there exists a minimum dominating set in G whose induced subgraph is an independent set. Finally, we characterize all unicyclic graphs G for which equality $$\tfrac{{n + 2 - \varepsilon (G)}} {3} = \gamma (G)$$ holds and we show that the length of the unique cycle of any unicyclic graph G with $$\tfrac{{n + 2 - \varepsilon (G)}} {3} = \gamma (G)$$ belongs to {4} ∪ {3, 6, 9, ...}. [ABSTRACT FROM AUTHOR]

( δ, g)-cage is a δ-regular graph with girth g and with the least possible number of vertices. In this paper, we show that all ( δ, g)-cages with odd girth g ≥ 9 are r-connected, where ( r − 1) ≤ δ + $ \sqrt \delta $ − 2 < r and all ( δ, g)-cages with even girth g ≥ 10 are r-connected, where r is the largest integer satisfying $ \frac{{r\left( {r - 1} \right)^2 }} {4} + 1 + 2r\left( {r - 1} \right) \leqslant \delta $. These results support a conjecture of Fu, Huang and Rodger that all ( δ, g)-cages are δ-connected. [ABSTRACT FROM AUTHOR]

graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G be the subgraph of G induced on the vertex set V ( G)\ { c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ( R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G has at least two connected components. We prove that the diameter of the induced graph G is two if Z( R) ≠ {0}, Z( R) = {0} and G is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z( R)* \ { c} such that the ideal [ N( α) ∩ N( β)]∪ {0} is generated by only one element of Z( R)*\{ c}. We also completely determine the correspondence between commutative rings and finite complete graphs K with some end vertices adjacent to a single vertex of K. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n. The diameter of a graph is the maximum distance between any two vertices of G. In this paper, we will give some bounds on the diameter of G in terms of eigenvalues of adjacency matrix and Laplacian matrix, respectively. [ABSTRACT FROM AUTHOR]