All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 4 Next

Displaying 61 – 80 of 102

Showing per page

On the number of spanning trees, the Laplacian eigenvalues, and the Laplacian Estrada index of subdivided-line graphs

Yilun Shang (2016)

Open Mathematics

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

On the rainbow connection of Cartesian products and their subgraphs

Sandi Klavžar, Gašper Mekiš (2012)

Discussiones Mathematicae Graph Theory

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

On the strong metric dimension of the strong products of graphs

Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez (2015)

Open Mathematics

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

On the Total Graph of Mycielski Graphs, Central Graphs and Their Covering Numbers

H.P. Patil, R. Pandiya Raj (2013)

Discussiones Mathematicae Graph Theory

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.

On the total restrained domination number of direct products of graphs

Wai Chee Shiu, Hong-Yu Chen, Xue-Gang Chen, Pak Kiu Sun (2012)

Discussiones Mathematicae Graph Theory

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 γ r t ( G ) , 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...

On the Vertex Separation of Maximal Outerplanar Graphs

Markov, Minko (2008)

Serdica Journal of Computing

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.

On Unique Minimum Dominating Sets in Some Cartesian Product Graphs

Jason T. Hedetniemi (2015)

Discussiones Mathematicae Graph Theory

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.

Oriented colouring of some graph products

N.R. Aravind, N. Narayanan, C.R. Subramanian (2011)

Discussiones Mathematicae Graph Theory

We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs.

Perfect Set of Euler Tours of Kp,p,p

T. Govindan, A. Muthusamy (2016)

Discussiones Mathematicae Graph Theory

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.

Products Of Digraphs And Their Competition Graphs

Martin Sonntag, Hanns-Martin Teichert (2016)

Discussiones Mathematicae Graph Theory

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.

Products of Geodesic Graphs and the Geodetic Number of Products

Jake A. Soloff, Rommy A. Márquez, Louis M. Friedler (2015)

Discussiones Mathematicae Graph Theory

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.

Rank numbers for bent ladders

Peter Richter, Emily Leven, Anh Tran, Bryan Ek, Jobby Jacob, Darren A. Narayan (2014)

Discussiones Mathematicae Graph Theory

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

Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs

Yuefang Sun (2016)

Discussiones Mathematicae Graph Theory

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

Some globally determined classes of graphs

Ivica Bošnjak, Rozália Madarász (2018)

Czechoslovak Mathematical Journal

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.

Some properties of the distance Laplacian eigenvalues of a graph

Mustapha Aouchiche, Pierre Hansen (2014)

Czechoslovak Mathematical Journal

The distance Laplacian of a connected graph G is defined by ℒ = Diag ( Tr ) - 𝒟 , where 𝒟 is the distance matrix of G , and Diag ( Tr ) is the diagonal matrix whose main entries are the vertex transmissions in G . The spectrum of ℒ is called the distance Laplacian spectrum of G . 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...

Spanning tree congestion of rook's graphs

Kyohei Kozawa, Yota Otachi (2011)

Discussiones Mathematicae Graph Theory

Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.

Currently displaying 61 – 80 of 102