ترغب بنشر مسار تعليمي؟ اضغط هنا

Prime Power and Prime Product Distance Graphs

58   0   0.0 ( 0 )
 نشر من قبل Josh Laison
 تاريخ النشر 2016
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

A graph $G$ is a $k$-prime product distance graph if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the product of at most $k$ primes. A graph has prime product number $ppn(G)=k$ if it is a $k$-prime product graph but not a $(k-1)$-prime product graph. Similarly, $G$ is a prime $k$th-power graph (respectively, strict prime $k$th-power graph) if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the $j$th power of a prime, for $j leq k$ (respectively, the $k$th power of a prime exactly). We prove that $ppn(K_n) = lceil log_2(n)rceil - 1$, and for a nonempty $k$-chromatic graph $G$, $ppn(G) = lceil log_2(k)rceil - 1$ or $ppn(G) = lceil log_2(k)rceil$. We determine $ppn(G)$ for all complete bipartite, 3-partite, and 4-partite graphs. We prove that $K_n$ is a prime $k$th-power graph if and only if $n < 7$, and we determine conditions on cycles and outerplanar graphs $G$ for which $G$ is a strict prime $k$th-power graph. We find connections between prime product and prime power distance graphs and the Twin Prime Conjecture, the Green-Tao Theorem, and Fermats Last Theorem.



قيم البحث

اقرأ أيضاً

A coprime labeling of a simple graph of order $n$ is a labeling in which adjacent vertices are given relatively prime labels, and a graph is prime if the labels used can be taken to be the first $n$ positive integers. In this paper, we consider when ladder graphs are prime and when the corresponding labeling may be done in a cyclic manner around the vertices of the ladder. Furthermore, we discuss coprime labelings for complete bipartite graphs.
123 - Ji Li 2009
In this paper, we enumerate prime graphs with respect to the Cartesian multiplication of graphs. We use the unique factorization of a connected graph into the product of prime graphs given by Sabidussi to find explicit formulas for labeled and unlabe led prime graphs. In the case of species, we construct the exponential composition of species based on the arithmetic product of species of Maia and Mendez and the quotient species, and express the species of connected graphs as the exponential composition of the species of prime graphs.
We explore graph theoretical properties of minimal prime graphs of finite solvable groups. In finite group theory studying the prime graph of a group has been an important topic for the past almost half century. Recently prime graphs of solvable grou ps have been characterized in graph theoretical terms only. This now allows the study of these graphs with methods from graph theory only. Minimal prime graphs turn out to be of particular interest, and in this paper we pursue this further by exploring, among other things, diameters, Hamiltonian cycles and the property of being self-complementary for minimal prime graphs. We also study a new, but closely related notion of minimality for prime graphs and look into counting minimal prime graphs.
A simple $n$-vertex graph has a prime vertex labeling if the vertices can be injectively labeled with the integers $1, 2, 3,ldots, n$ such that adjacent vertices have relatively prime labels. We will present previously unknown prime vertex labelings for new families of graphs, all of which are special cases of Seoud and Youssefs conjecture that all unicyclic graphs have a prime labeling.
A simple and connected $n$-vertex graph has a prime vertex labeling if the vertices can be injectively labeled with the integers $1, 2, 3,ldots, n$, such that adjacent vertices have relatively prime labels. We will present previously unknown prime ve rtex labelings for new families of graphs including cycle pendant stars, cycle chains, prisms, and generalized books.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا