Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Total Acquisition Number of the Randomly Weighted Path
74
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
There exists a significant body of work on determining the acquisition number $a_t(G)$ of various graphs when the vertices of those graphs are each initially assigned a unit weight. We determine properties of the acquisition number of the path, star, complete, complete bipartite, cycle, and wheel graphs for variations on this initial weighting scheme, with the majority of our work focusing on the expected acquisition number of randomly weighted graphs. In particular, we bound the expected acquisition number $E(a_t(P_n))$ of the $n$-path when $n$ distinguishable units of integral weight, or chips, are randomly distributed across its vertices between $0.242n$ and $0.375n$. With computer support, we improve it by showing that $E(a_t(P_n))$ lies between $0.29523n$ and $0.29576n$. We then use subadditivity to show that the limiting ratio $lim E(a_t(P_n))/n$ exists, and simulations reveal more exactly what the limiting value equals. The Hoeffding-Azuma inequality is used to prove that the acquisition number is tightly concentrated around its expected value. Additionally, in a different context, we offer a non-optimal acquisition protocol algorithm for the randomly weighted path and exactly compute the expected size of the resultant residual set.
rate research
Read More
The Turan number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. Let P_k be the path with k vertices, the square P^2_k of P_k is obtained by joining the pairs of vertices with distance one or two in P_k. The powerful theorem of ErdH{o}s, Stone and Simonovits determines the asymptotic behavior of ex(n,P^2_k). In the present paper, we determine the exact value of ex(n,P^2_5) and ex(n,P^2_6) and pose a conjecture for the exact value of ex(n,P^2_k).
A total dominator coloring of a graph G is a proper coloring of G in which each vertex of the graph is adjacent to every vertex of some color class. The total dominator chromatic number of a graph is the minimum number of color classes in a total dominator coloring. In this article, we study the total dominator coloring on middle graphs by giving several bounds for the case of general graphs and trees. Moreover, we calculate explicitely the total dominator chromatic number of the middle graph of several known families of graphs.
When considering binary strings, its natural to wonder how many distinct subsequences might exist in a given string. Given that there is an existing algorithm which provides a straightforward way to compute the number of distinct subsequences in a fixed string, we might next be interested in the expected number of distinct subsequences in random strings. This expected value is already known for random binary strings where each letter in the string is, independently, equally likely to be a 1 or a 0. We generalize this result to random strings where the letter 1 appears independently with probability $alpha in [0,1]$. Also, we make some progress in the case of random strings from an arbitrary alphabet as well as when the string is generated by a two-state Markov chain.
A $k$-tuple total dominating set ($k$TDS) of a graph $G$ is a set $S$ of vertices in which every vertex in $G$ is adjacent to at least $k$ vertices in $S$. The minimum size of a $k$TDS is called the $k$-tuple total dominating number and it is denoted by $gamma_{times k,t}(G)$. We give a constructive proof of a general formula for $gamma_{times 3, t}(K_n Box K_m)$.
Let $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a,b,c,d,e,f,g$ and 3 edges ${a,b,c}, {c,d,e},$ and ${e,f,g}$. It is known that the $r$-color Ramsey number for $P$ is $R(P;r)=r+6$ for $rle 9$. The proof of this result relies on a careful analysis of the Turan numbers for $P$. In this paper, we refine this analysis further and compute the fifth order Turan number for $P$, for all $n$. Using this number for $n=16$, we confirm the formula $R(P;10)=16$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
