The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying 61 –
80 of
103
Let (−→ Cm2−→ Cn) be the domination number of the Cartesian product of directed cycles −→ Cm and −→ Cn for m, n ≥ 2. Shaheen [13] and Liu et al. ([11], [12]) determined the value of (−→ Cm2−→ Cn) when m ≤ 6 and [12] when both m and n ≡ 0(mod 3). In this article we give, in general, the value of (−→ Cm2−→ Cn) when m ≡ 2(mod 3) and improve the known lower bounds for most of the remaining cases. We also disprove the conjectured formula for the case m ≡ 0(mod 3) appearing in [12].
As a generalization of the Sierpiński-like graphs, the subdivided-line graph Г(G) of a simple connected graph G is defined to be the line graph of the barycentric subdivision of G. In this paper we obtain a closed-form formula for the enumeration of spanning trees in Г(G), employing the theory of electrical networks. We present bounds for the largest and second smallest Laplacian eigenvalues of Г(G) in terms of the maximum degree, the number of edges, and the first Zagreb index of G. In addition,...
Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed....
Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study...
The technique of counting cliques in networks is a natural problem. In this paper, we develop certain results on counting of triangles for the total graph of the Mycielski graph or central graph of star as well as completegraph families. Moreover, we discuss the upper bounds for the number of triangles in the Mycielski and other well known transformations of graphs. Finally, it is shown that the achromatic number and edge-covering number of the transformations mentioned above are equated.
Let G = (V,E) be a graph. A total restrained dominating set is a set S ⊆ V where every vertex in V∖S is adjacent to a vertex in S as well as to another vertex in V∖S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by , is the smallest cardinality of a total restrained dominating set of G. We determine lower and upper bounds on the total restrained domination number of the direct product of two graphs. Also, we show that these bounds...
We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex
separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.
Unique minimum vertex dominating sets in the Cartesian product of a graph with a complete graph are considered. We first give properties of such sets when they exist. We then show that when the first factor of the product is a tree, consideration of the tree alone is sufficient to determine if the product has a unique minimum dominating set.
We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs.
Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G, is Hamilton cycle decomposable. In this paper, we construct a perfect set of Euler tours for the complete tripartite graph Kp,p,p for any prime p and hence prove Bermond’s conjecture for G = Kp,p,p.
If D = (V, A) is a digraph, its competition graph (with loops) CGl(D) has the vertex set V and {u, v} ⊆ V is an edge of CGl(D) if and only if there is a vertex w ∈ V such that (u, w), (v, w) ∈ A. In CGl(D), loops {v} are allowed only if v is the only predecessor of a certain vertex w ∈ V. For several products D1 ⚬ D2 of digraphs D1 and D2, we investigate the relations between the competition graphs of the factors D1, D2 and the competition graph of their product D1 ⚬ D2.
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.
A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices with the same label contains a vertex with a larger label. The rank number of a graph is the fewest number of labels that can be used in a ranking. The rank number of a graph is known for many families, including the ladder graph P2 × Pn. We consider how ”bending” a ladder affects the rank number. We prove that in certain cases the rank number does not change, and in others the rank...
The generalized k-connectivity κk(G) of a graph G was introduced by Hager in 1985. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λk(G) = min{λ(S) : S ⊆ V (G) and |S| = k}, where λ(S) denote the maximum number ℓ of pairwise edge-disjoint trees T1, T2, . . . , Tℓ in G such that S ⊆ V (Ti) for 1 ≤ i ≤ ℓ. In this paper, we study the generalized edge- connectivity of product graphs and obtain sharp upper bounds...
For a class of graphs we say that it is globally determined if any two nonisomorphic graphs from that class have nonisomorphic globals. We will prove that the class of so called CCB graphs and the class of finite forests are globally determined.
The distance Laplacian of a connected graph is defined by , where is the distance matrix of , and is the diagonal matrix whose main entries are the vertex transmissions in . The spectrum of is called the distance Laplacian spectrum of . In the present paper, we investigate some particular distance Laplacian eigenvalues. Among other results, we show that the complete graph is the unique graph with only two distinct distance Laplacian eigenvalues. We establish some properties of the distance...
Currently displaying 61 –
80 of
103