Packing four copies of a tree into a complete bipartite graph

Liqun Pu; Yuan Tang; Xiaoli Gao

Displaying similar documents to “Packing four copies of a tree into a complete bipartite graph”

A note on the open packing number in graphs

Mehdi Mohammadi, Mohammad Maghasedi (2019)

Mathematica Bohemica

Similarity:

A subset $S$ of vertices in a graph $G$ is an open packing set if no pair of vertices of $S$ has a common neighbor in $G$ . An open packing set which is not a proper subset of any open packing set is called a maximal open packing set. The maximum cardinality of an open packing set is called the open packing number and is denoted by $ρ^{o} (G)$ . A subset $S$ in a graph $G$ with no isolated vertex is called a total dominating set if any vertex of $G$ is adjacent to some vertex of $S$ . The total domination number...

On the asymptotics of counting functions for Ahlfors regular sets

Dušan Pokorný, Marc Rauch (2022)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We deal with the so-called Ahlfors regular sets (also known as $s$ -regular sets) in metric spaces. First we show that those sets correspond to a certain class of tree-like structures. Building on this observation we then study the following question: Under which conditions does the limit ${lim}_{ε \to 0 +} ε^{s} N (ε, K)$ exist, where $K$ is an $s$ -regular set and $N (ε, K)$ is for instance the $ε$ -packing number of $K$ ?

Perturbing the hexagonal circle packing: a percolation perspective

Itai Benjamini, Alexandre Stauffer (2013)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider the hexagonal circle packing with radius $1 / 2$ and perturb it by letting the circles move as independent Brownian motions for time $t$ . It is shown that, for large enough $t$ , if $𝛱_{t}$ is the point process given by the center of the circles at time $t$ , then, as $t \to \infty$ , the critical radius for circles centered at $𝛱_{t}$ to contain an infinite component converges to that of continuum percolation (which was shown – based on a Monte Carlo estimate – by Balister, Bollobás and Walters to be strictly...

On a characterization of $k$ -trees

De-Yan Zeng, Jian Hua Yin (2015)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a $k$ -tree if either $G$ is the complete graph on $k + 1$ vertices, or $G$ has a vertex $v$ whose neighborhood is a clique of order $k$ and the graph obtained by removing $v$ from $G$ is also a $k$ -tree. Clearly, a $k$ -tree has at least $k + 1$ vertices, and $G$ is a 1-tree (usual tree) if and only if it is a $1$ -connected graph and has no $K_{3}$ -minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of $k$ -trees as follows: if $G$ is a graph with at least $k + 1$ vertices, then $G$ is...

A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs

Yaping Mao, Christopher Melekian, Eddie Cheng (2023)

Czechoslovak Mathematical Journal

Similarity:

For a connected graph $G = (V, E)$ and a set $S \subseteq V (G)$ with at least two vertices, an $S$ -Steiner tree is a subgraph $T = (V^{'}, E^{'})$ of $G$ that is a tree with $S \subseteq V^{'}$ . If the degree of each vertex of $S$ in $T$ is equal to 1, then $T$ is called a pendant $S$ -Steiner tree. Two $S$ -Steiner trees are if they share no vertices other than $S$ and have no edges in common. For $S \subseteq V (G)$ and $| S | \geq 2$ , the pendant tree-connectivity $τ_{G} (S)$ is the maximum number of internally disjoint pendant $S$ -Steiner trees in $G$ , and for $k \geq 2$ , the $k$ -pendant tree-connectivity $τ_{k} (G)$ is the...

Continuous rearrangements of the Haar system in $H_{p}$ for 0 < p < ∞

Krzysztof Smela (2008)

Studia Mathematica

Similarity:

We prove three theorems on linear operators $T_{τ, p} : H_{p} (ℬ) \to H_{p}$ induced by rearrangement of a subsequence of a Haar system. We find a sufficient and necessary condition for $T_{τ, p}$ to be continuous for 0 < p < ∞.

On the domination of triangulated discs

Noor A&amp;#039;lawiah Abd Aziz, Nader Jafari Rad, Hailiza Kamarulhaili (2023)

Mathematica Bohemica

Similarity:

Let $G$ be a $3$ -connected triangulated disc of order $n$ with the boundary cycle $C$ of the outer face of $G$ . Tokunaga (2013) conjectured that $G$ has a dominating set of cardinality at most $\frac{1}{4} (n + 2)$ . This conjecture is proved in Tokunaga (2020) for $G - C$ being a tree. In this paper we prove the above conjecture for $G - C$ being a unicyclic graph. We also deduce some bounds for the double domination number, total domination number and double total domination number in triangulated discs.

Horocyclic products of trees

Laurent Bartholdi, Markus Neuhauser, Wolfgang Woess (2008)

Journal of the European Mathematical Society

Similarity:

Let $T_{1}, \dots, T_{d}$ be homogeneous trees with degrees $q_{1} + 1, \dots, q_{d} + 1 \geq 3$ , respectively. For each tree, let $𝔥 : T_{j} \to ℤ$ be the Busemann function with respect to a fixed boundary point (end). Its level sets are the horocycles. The horocyclic product of $T_{1}, \dots, T_{d}$ is the graph $𝖣𝖫 (q_{1}, \dots, q_{d})$ consisting of all $d$ -tuples $x_{1} \dots x_{d} \in T_{1} \times \dots \times T_{d}$ with $𝔥 (x_{1}) + \dots + 𝔥 (x_{d}) = 0$ , equipped with a natural neighbourhood relation. In the present paper, we explore the geometric, algebraic, analytic and probabilistic properties of these graphs and their isometry groups. If $d = 2$ and $q_{1} = q_{2} = q$ then we obtain a Cayley graph...

Saturation numbers for linear forests $P_{6} + t P_{2}$

Jingru Yan (2023)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is $H$ -saturated if it contains no $H$ as a subgraph, but does contain $H$ after the addition of any edge in the complement of $G$ . The saturation number, $sat (n, H)$ , is the minimum number of edges of a graph in the set of all $H$ -saturated graphs of order $n$ . We determine the saturation number $sat (n, P_{6} + t P_{2})$ for $n \geq \frac{10}{3} t + 10$ and characterize the extremal graphs for $n > \frac{10}{3} t + 20$ .

The relation between the number of leaves of a tree and its diameter

Pu Qiao, Xingzhi Zhan (2022)

Czechoslovak Mathematical Journal

Similarity:

Let $L (n, d)$ denote the minimum possible number of leaves in a tree of order $n$ and diameter $d .$ Lesniak (1975) gave the lower bound $B (n, d) = ⌈ 2 (n - 1) / d ⌉$ for $L (n, d) .$ When $d$ is even, $B (n, d) = L (n, d) .$ But when $d$ is odd, $B (n, d)$ is smaller than $L (n, d)$ in general. For example, $B (21, 3) = 14$ while $L (21, 3) = 19 .$ In this note, we determine $L (n, d)$ using new ideas. We also consider the converse problem and determine the minimum possible diameter of a tree with given order and number of leaves.

On γ-labelings of trees

Gary Chartrand, David Erwin, Donald W. VanderJagt, Ping Zhang (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G) → 0,1,2,...,m that induces a labeling f’: E(G) → 1,2,...,m of the edges of G defined by f’(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is $v a l (f) = Σ_{e \in E (G)} f^{'} K (e)$ . The maximum value of a γ-labeling of G is defined as $v a l_{m a x} (G) = m a x v a l (f) : f i s a γ - l a b e l i n g o f G$ ; while the minimum value of a γ-labeling of G is $v a l_{m i n} (G) = m i n v a l (f) : f i s a γ - l a b e l i n g o f G$ ; The values $v a l_{m a x} (S_{p, q})$ and $v a l_{m i n} (S_{p, q})$ are determined for double stars $S_{p, q}$ . We present characterizations of connected graphs G of order n for which...

Some properties of packing measure with doubling gauge

Sheng-You Wen, Zhi-Ying Wen (2004)

Studia Mathematica

Similarity:

Let g be a doubling gauge. We consider the packing measure $^{g}$ and the packing premeasure $₀^{g}$ in a metric space X. We first show that if $₀^{g} (X)$ is finite, then as a function of X, $₀^{g}$ has a kind of “outer regularity”. Then we prove that if X is complete separable, then $λ s u p ₀^{g} (F) \leq^{g} (B) \leq s u p ₀^{g} (F)$ for every Borel subset B of X, where the supremum is taken over all compact subsets of B having finite $₀^{g}$ -premeasure, and λ is a positive number depending only on the doubling gauge g. As an application, we show that for every doubling...

Matchings in complete bipartite graphs and the $r$ -Lah numbers

Gábor Nyul, Gabriella Rácz (2021)

Czechoslovak Mathematical Journal

Similarity:

We give a graph theoretic interpretation of $r$ -Lah numbers, namely, we show that the $r$ -Lah number ${⌊\binom{n}{k}⌋}_{r}$ counting the number of $r$ -partitions of an $(n + r)$ -element set into $k + r$ ordered blocks is just equal to the number of matchings consisting of $n - k$ edges in the complete bipartite graph with partite sets of cardinality $n$ and $n + 2 r - 1$ ( $0 \leq k \leq n$ , $r \geq 1$ ). We present five independent proofs including a direct, bijective one. Finally, we close our work with a similar result for $r$ -Stirling numbers of the second kind. ...

The Turán number of the graph $3 P_{4}$

Halina Bielak, Sebastian Kieliszek (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let $e x (n, G)$ denote the maximum number of edges in a graph on $n$ vertices which does not contain $G$ as a subgraph. Let $P_{i}$ denote a path consisting of $i$ vertices and let $m P_{i}$ denote $m$ disjoint copies of $P_{i}$ . In this paper we count $e x (n, 3 P_{4})$ .

The small Ree group $^{2} G_{2} (3^{2 n + 1})$ and related graph

Alireza K. Asboei, Seyed S. S. Amiri (2018)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let $G$ be a finite group. The main supergraph $𝒮 (G)$ is a graph with vertex set $G$ in which two vertices $x$ and $y$ are adjacent if and only if $o (x) ∣ o (y)$ or $o (y) ∣ o (x)$ . In this paper, we will show that $G ≅^{2} G_{2} (3^{2 n + 1})$ if and only if $𝒮 (G) ≅ 𝒮 (^{2} G_{2} (3^{2 n + 1}))$ . As a main consequence of our result we conclude that Thompson’s problem is true for the small Ree group $^{2} G_{2} (3^{2 n + 1})$ .

Spanning trees whose reducible stems have a few branch vertices

Pham Hoang Ha, Dang Dinh Hanh, Nguyen Thanh Loan, Ngoc Diep Pham (2021)

Czechoslovak Mathematical Journal

Similarity:

Let $T$ be a tree. Then a vertex of $T$ with degree one is a leaf of $T$ and a vertex of degree at least three is a branch vertex of $T$ . The set of leaves of $T$ is denoted by $L (T)$ and the set of branch vertices of $T$ is denoted by $B (T)$ . For two distinct vertices $u$ , $v$ of $T$ , let $P_{T} [u, v]$ denote the unique path in $T$ connecting $u$ and $v .$ Let $T$ be a tree with $B (T) \neq \emptyset$ . For each leaf $x$ of $T$ , let $y_{x}$ denote the nearest branch vertex to $x$ . We delete $V (P_{T} [x, y_{x}]) ∖ {y_{x}}$ from $T$ for all $x \in L (T)$ . The resulting subtree of $T$ is called the reducible stem...