Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the decomposition threshold of a given graph
116
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the $F$-decomposition threshold $delta_F$ for a given graph $F$. Here an $F$-decomposition of a graph $G$ is a collection of edge-disjoint copies of $F$ in $G$ which together cover every edge of $G$. (Such an $F$-decomposition can only exist if $G$ is $F$-divisible, i.e. if $e(F)mid e(G)$ and each vertex degree of $G$ can be expressed as a linear combination of the vertex degrees of $F$.) The $F$-decomposition threshold $delta_F$ is the smallest value ensuring that an $F$-divisible graph $G$ on $n$ vertices with $delta(G)ge(delta_F+o(1))n$ has an $F$-decomposition. Our main results imply the following for a given graph $F$, where $delta_F^ast$ is the fractional version of $delta_F$ and $chi:=chi(F)$: (i) $delta_Fle max{delta_F^ast,1-1/(chi+1)}$; (ii) if $chige 5$, then $delta_Fin{delta_F^{ast},1-1/chi,1-1/(chi+1)}$; (iii) we determine $delta_F$ if $F$ is bipartite. In particular, (i) implies that $delta_{K_r}=delta^ast_{K_r}$. Our proof involves further developments of the recent `iterative absorbing approach.
rate research
Read More
Let $G$ be a graph and $tau$ be an assignment of nonnegative integer thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a $tau$-dynamic monopoly, if $V(G)$ can be partitioned into subsets $D_0, D_1, ldots, D_k$ such that $D_0=D$ and for any $iin {0, ldots, k-1}$, each vertex $v$ in $D_{i+1}$ has at least $tau(v)$ neighbors in $D_0cup ldots cup D_i$. Denote the size of smallest $tau$-dynamic monopoly by $dyn_{tau}(G)$ and the average of thresholds in $tau$ by $overline{tau}$. We show that the values of $dyn_{tau}(G)$ over all assignments $tau$ with the same average threshold is a continuous set of integers. For any positive number $t$, denote the maximum $dyn_{tau}(G)$ taken over all threshold assignments $tau$ with $overline{tau}leq t$, by $Ldyn_t(G)$. In fact, $Ldyn_t(G)$ shows the worst-case value of a dynamic monopoly when the average threshold is a given number $t$. We investigate under what conditions on $t$, there exists an upper bound for $Ldyn_{t}(G)$ of the form $c|G|$, where $c<1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar graphs but has polynomial-time solution for forests.
The degree set of a finite simple graph $G$ is the set of distinct degrees of vertices of $G$. A theorem of Kapoor, Polimeni & Wall asserts that the least order of a graph with a given degree set $mathscr D$ is $1+max mathscr D$. Tripathi & Vijay considered the analogous problem concerning the least size of graphs with degree set $mathscr D$. We expand on their results, and determine the least size of graphs with degree set $mathscr D$ when (i) $min mathscr D mid d$ for each $d in mathscr D$; (ii) $min mathscr D=2$; (iii) $mathscr D={m,m+1,ldots,n}$. In addition, given any $mathscr D$, we produce a graph $G$ whose size is within $min mathscr D$ of the optimal size, giving a $big(1+frac{2}{d_1+1})$-approximation, where $d_1=max mathscr D$.
An edge-colored connected graph $G$ is properly connected if between every pair of distinct vertices, there exists a path that no two adjacent edges have a same color. Fujita (2019) introduced the optimal proper connection number ${mathrm{pc}_{mathrm{opt}}}(G)$ for a monochromatic connected graph $G$, to make a connected graph properly connected efficiently. More precisely, ${mathrm{pc}_{mathrm{opt}}}(G)$ is the smallest integer $p+q$ when one converts a given monochromatic graph $G$ into a properly connected graph by recoloring $p$ edges with $q$ colors. In this paper, we show that ${mathrm{pc}_{mathrm{opt}}}(G)$ has an upper bound in terms of the independence number $alpha(G)$. Namely, we prove that for a connected graph $G$, ${mathrm{pc}_{mathrm{opt}}}(G)le frac{5alpha(G)-1}{2}$. Moreoevr, for the case $alpha(G)leq 3$, we improve the upper bound to $4$, which is tight.
Motivated by work of ErdH{o}s, Ota determined the maximum size $g(n,k)$ of a $k$-connected nonhamiltonian graph of order $n$ in 1995. But for some pairs $n,k,$ the maximum size is not attained by a graph of connectivity $k.$ For example, $g(15,3)=77$ is attained by a unique graph of connectivity $7,$ not $3.$ In this paper we obtain more precise information by determining the maximum size of a nonhamiltonian graph of order $n$ and connectivity $k,$ and determining the extremal graphs. Consequently we solve the corresponding problem for nontraceable graphs.
We introduce a graph decomposition which exists for all simple, connected graphs $G=(V,E)$. The decomposition $V = A cup B cup C$ is such that each vertex in $A$ has more neighbors in $B$ than in $A$ and vice versa. $C$ is `balanced: each $v in C$ has the same number of neighbours in $A$ and $B$. These decompositions arise naturally from the behavior of an associated dynamical system (`Randomized Rounding) on $(mathbb{S}^1)^{|V|}$. Connections to judicious partitions and the textsc{MaxCut} problem (in particular the Burer-Monteiro-Zhang heuristic) are being discussed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
