Wiener index of the tensor product of a path and a cycle

K. Pattabiraman; P. Paulraja

Displaying similar documents to “Wiener index of the tensor product of a path and a cycle”

Centers of n-fold tensor products of graphs

Sarah Bendall, Richard Hammack (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Formulas for vertex eccentricity and radius for the n-fold tensor product $G = \otimes_{i = 1} ⁿ G_{i}$ of n arbitrary simple graphs $G_{i}$ are derived. The center of G is characterized as the union of n+1 vertex sets of form V₁×V₂×...×Vₙ, with $V_{i} \subseteq V (G_{i})$ .

Pairs of forbidden class of subgraphs concerning $K_{1, 3}$ and P₆ to have a cycle containing specified vertices

Takeshi Sugiyama, Masao Tsugaki (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1, 3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1, 3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.

Histories in path graphs

Ludovít Niepel (2007)

Discussiones Mathematicae Graph Theory

Similarity:

For a given graph G and a positive integer r the r-path graph, $P_{r} (G)$ , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let $P_{r}^{k} (G)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_{r}^{k} (G)$ . The k-history $P_{r}^{- k} (H)$ is a subgraph of G that is induced by all edges that take part in the recursive...

Biduals of tensor products in operator spaces

Verónica Dimant, Maite Fernández-Unzueta (2015)

Studia Mathematica

Similarity:

We study whether the operator space $V * * \overset{α}{\otimes} W * *$ can be identified with a subspace of the bidual space $(V \overset{α}{\otimes} W) * *$ , for a given operator space tensor norm. We prove that this can be done if α is finitely generated and V and W are locally reflexive. If in addition the dual spaces are locally reflexive and the bidual spaces have the completely bounded approximation property, then the identification is through a complete isomorphism. When α is the projective, Haagerup or injective norm, the hypotheses can be...

Wiener and vertex PI indices of the strong product of graphs

K. Pattabiraman, P. Paulraja (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The Wiener index of a connected graph G, denoted by W(G), is defined as $½ \sum_{u, v \in V (G)} d_{G} (u, v)$ . Similarly, the hyper-Wiener index of a connected graph G, denoted by WW(G), is defined as $½ W (G) + ¼ \sum_{u, v \in V (G)} d ²_{G} (u, v)$ . The vertex Padmakar-Ivan (vertex PI) index of a graph G is the sum over all edges uv of G of the number of vertices which are not equidistant from u and v. In this paper, the exact formulae for Wiener, hyper-Wiener and vertex PI indices of the strong product $G ⊠ K_{m ₀, m ₁, . . ., m_{r - 1}}$ , where $K_{m ₀, m ₁, . . ., m_{r - 1}}$ is the complete multipartite graph with partite sets...

Chvátal's Condition cannot hold for both a graph and its complement

Alexandr V. Kostochka, Douglas B. West (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that $d_{i} > i$ or $d_{n - i} \geq n - i$ . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

The Wiener number of powers of the Mycielskian

Rangaswami Balakrishnan, S. Francis Raj (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The Wiener number of a graph G is defined as $1 / 2 \sum_{u, v \in V (G)} d (u, v)$ , d the distance function on G. The Wiener number has important applications in chemistry. We determine a formula for the Wiener number of an important graph family, namely, the Mycielskians μ(G) of graphs G. Using this, we show that for k ≥ 1, $W (μ (S ₙ^{k})) \leq W (μ (T ₙ^{k})) \leq W (μ (P ₙ^{k}))$ , where Sₙ, Tₙ and Pₙ denote a star, a general tree and a path on n vertices respectively. We also obtain Nordhaus-Gaddum type inequality for the Wiener number of $μ (G^{k})$ .

The induced paths in a connected graph and a ternary relation determined by them

Ladislav Nebeský (2002)

Mathematica Bohemica

Similarity:

By a ternary structure we mean an ordered pair $(X_{0}, T_{0})$ , where $X_{0}$ is a finite nonempty set and $T_{0}$ is a ternary relation on $X_{0}$ . By the underlying graph of a ternary structure $(X_{0}, T_{0})$ we mean the (undirected) graph $G$ with the properties that $X_{0}$ is its vertex set and distinct vertices $u$ and $v$ of $G$ are adjacent if and only if ${x \in X_{0} T_{0} (u, x, v)} \cup {x \in X_{0} T_{0} (v, x, u)} = {u, v} .$ A ternary structure $(X_{0}, T_{0})$ is said to be the B-structure of a connected graph $G$ if $X_{0}$ is the vertex set of $G$ and the following statement holds for all $u, x, y \in X_{0}$ : $T_{0} (x, u, y)$ if and only if $u$ belongs to an...

On the derived tensor product functors for (DF)- and Fréchet spaces

Oğuz Varol (2007)

Studia Mathematica

Similarity:

For a (DF)-space E and a tensor norm α we investigate the derivatives $T o r_{α}^{l} (E, \cdot)$ of the tensor product functor $E \otimes ̃_{α} \cdot : \to$ from the category of Fréchet spaces to the category of linear spaces. Necessary and sufficient conditions for the vanishing of $T o r ¹_{α} (E, F)$ , which is strongly related to the exactness of tensored sequences, are presented and characterizations in the nuclear and (co-)echelon cases are given.

How many are equiaffine connections with torsion

Zdeněk Dušek, Oldřich Kowalski (2015)

Archivum Mathematicum

Similarity:

The question how many real analytic equiaffine connections with arbitrary torsion exist locally on a smooth manifold $M$ of dimension $n$ is studied. The families of general equiaffine connections and with skew-symmetric Ricci tensor, or with symmetric Ricci tensor, respectively, are described in terms of the number of arbitrary functions of $n$ variables.

On-line ranking number for cycles and paths

Erik Bruoth, Mirko Horňák (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number $χ *_{r} (G)$ of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that $χ *_{r} (P ₙ) < 3 l o g ₂ n$ for n ≥ 2....

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.

On perfect and unique maximum independent sets in graphs

Lutz Volkmann (2004)

Mathematica Bohemica

Similarity:

A perfect independent set $I$ of a graph $G$ is defined to be an independent set with the property that any vertex not in $I$ has at least two neighbors in $I$ . For a nonnegative integer $k$ , a subset $I$ of the vertex set $V (G)$ of a graph $G$ is said to be $k$ -independent, if $I$ is independent and every independent subset $I^{'}$ of $G$ with $| I^{'} | \geq | I | - (k - 1)$ is a subset of $I$ . A set $I$ of vertices of $G$ is a super $k$ -independent set of $G$ if $I$ is $k$ -independent in the graph $G [I, V (G) - I]$ , where $G [I, V (G) - I]$ is the bipartite graph obtained from $G$ by deleting...

The path space of a higher-rank graph

Samuel B. G. Webster (2011)

Studia Mathematica

Similarity:

We construct a locally compact Hausdorff topology on the path space of a finitely aligned k-graph Λ. We identify the boundary-path space ∂Λ as the spectrum of a commutative C*-subalgebra $D_{Λ}$ of C*(Λ). Then, using a construction similar to that of Farthing, we construct a finitely aligned k-graph Λ̃ with no sources in which Λ is embedded, and show that ∂Λ is homeomorphic to a subset of ∂Λ̃. We show that when Λ is row-finite, we can identify C*(Λ) with a full corner of C*(Λ̃), and deduce...

On the Dunford-Pettis property of tensor product spaces

Ioana Ghenciu (2011)

Colloquium Mathematicae

Similarity:

We give sufficient conditions on Banach spaces E and F so that their projective tensor product $E \otimes_{π} F$ and the duals of their projective and injective tensor products do not have the Dunford-Pettis property. We prove that if E* does not have the Schur property, F is infinite-dimensional, and every operator T:E* → F** is completely continuous, then $(E \otimes_{ϵ} F) *$ does not have the DPP. We also prove that if E* does not have the Schur property, F is infinite-dimensional, and every operator T: F** → E* is...