EuDML | Browse

The cubical dimension of a graph $G$ is the smallest dimension of a hypercube into which $G$ is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with $2^{n}$ vertices, $n \geq 1$ , is $n$ . The 2-rooted complete binary tree of depth $n$ is obtained from two copies of the complete binary tree of depth $n$ by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted...

A note on the independent domination number versus the domination number in bipartite graphs

Shaohui Wang, Bing Wei (2017)

Czechoslovak Mathematical Journal

Let $γ (G)$ and $i (G)$ be the domination number and the independent domination number of $G$ , respectively. Rad and Volkmann posted a conjecture that $i (G) / γ (G) \leq Δ (G) / 2$ for any graph $G$ , where $Δ (G)$ is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than $Δ (G) / 2$ are provided as well.

A parametric analysis of the largest induced tree problem in random graphs

M. Protasi, M. Talamo (1986)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A partition of connected graphs.

Wiseman, Gus (2005)

The Electronic Journal of Combinatorics [electronic only]

A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree.

Iksanov, Alex, Möhle, Martin (2007)

Electronic Communications in Probability [electronic only]

A refinement of the formula for $k$ -ary trees and the Gould-Vandermonde's convolution.

Chen, Ricky X.F. (2008)

The Electronic Journal of Combinatorics [electronic only]

A remark on branch weights in countable trees

Bohdan Zelinka (2004)

Mathematica Bohemica

Let $T$ be a tree, let $u$ be its vertex. The branch weight $b (u)$ of $u$ is the maximum number of vertices of a branch of $T$ at $u$ . The set of vertices $u$ of $T$ in which $b (u)$ attains its minimum is the branch weight centroid $B (T)$ of $T$ . For finite trees the present author proved that $B (T)$ coincides with the median of $T$ , therefore it consists of one vertex or of two adjacent vertices. In this paper we show that for infinite countable trees the situation is quite different.

Currently displaying 21 – 40 of 593

Previous Page 2 Next

Displaying 21 – 40 of 593

A modification of the median of a tree

A multivariate Lagrange inversion formula for asymptotic calculations.

A New Approach to the Dynamic Maintenance of Maximal Points in a Plane.

A new spectral method for determining the number of spanning trees.

A note on embedding hypertrees.

A note on major sequences and external activity in trees.

A note on minimum rank and maximum nullity of sign patterns.

A note on naturally embedded ternary trees.

A note on random minimum length spanning trees.

A note on reconstructing of finite trees from small subtrees

A note on the cubical dimension of new classes of binary trees