Hop total Roman domination in graphs
- 1. Babol Noshirvani University of Technology
- 2. University of Blida
- 3. Azarbaijan Shahid Madani University
Description
In this article, we initiate a study of hop total Roman domination defined as follows: a hop total Roman dominating function (HTRDF) on a graph G=(V,E) is a function f:V→{0,1,2} such that for every vertex u with f(u) = 0 there exists a vertex v at distance 2 from u with f(v) = 2 and the subgraph induced by the vertices assigned non-zero values under f has no isolated vertices. The weight of an HTRDF is the sum of its function values over all vertices, and the hop total Roman domination number γdtR(G) equals the minimum weight of an HTRDF on G. We provide several properties on the hop total Roman domination number. More precisely, we show that the decision problem corresponding to the hop total Roman domination problem is NP-complete for bipartite graphs, and we determine the exact value of γhtR(G) for paths and cycles. Moreover, we characterize all connected graphs G of order n with γhtR(G)∈{2,3,4,n}. Finally, we show that for every tree T of diameter at least 3, γhtR(T)≥γht(T)+2, where γht(T) is the hop total domination number.
Translated Descriptions
Translated Description (Arabic)
في هذه المقالة، نبدأ دراسة الهيمنة الرومانية الكلية للقفز المعرفة على النحو التالي: الدالة المسيطرة الرومانية الكلية للقفز (HTRDF) على الرسم البياني G=(V،E) هي دالة f:V→{0،1،2} بحيث أنه لكل رأس u مع f(u) = 0 يوجد رأس v على مسافة 2 من u مع f(v) = 2 والرسم البياني الفرعي المستحث بالرؤوس المعينة قيم غير صفرية تحت f ليس له رؤوس معزولة. وزن HTRDF هو مجموع قيم وظيفته على جميع الرؤوس، ورقم الهيمنة الرومانية الإجمالية HOP γdtR (G) يساوي الحد الأدنى لوزن HTRDF على G. نحن نقدم العديد من الخصائص على رقم الهيمنة الرومانية الإجمالية HOP. بتعبير أدق، نظهر أن مشكلة القرار المقابلة لمشكلة الهيمنة الرومانية الكلية لـ HOP هي NP - complete للرسوم البيانية ثنائية الجانب، ونحدد القيمة الدقيقة لـγhtR (G) للمسارات والدورات. علاوة على ذلك، نقوم بتوصيف جميع الرسوم البيانية المتصلة G من الترتيب n باستخدامγhtR (G)? {2,3,4,n}. أخيرًا، نظهر أنه لكل شجرة T قطرها 3 على الأقل، γhtR (T)≥ γht (T)+2، حيث γht(T) هو رقم الهيمنة الكلية للقفز.Translated Description (French)
Dans cet article, nous commençons une étude de la domination romaine totale du saut définie comme suit : une fonction de domination romaine totale du saut (HTRDF) sur un graphique G=(V,E) est une fonction f :V→{0,1,2} telle que pour chaque sommet u avec f(u) = 0, il existe un sommet v à la distance 2 de u avec f(v) = 2 et le sous-graphe induit par les sommets affectés de valeurs non nulles sous f n'a pas de sommets isolés. Le poids d'un HTRDF est la somme de ses valeurs de fonction sur tous les sommets, et le nombre total de domination romaine de saut γdtR (G) est égal au poids minimum d'un HTRDF sur G. Nous fournissons plusieurs propriétés sur le nombre total de domination romaine de saut. Plus précisément, nous montrons que le problème de décision correspondant au problème de domination romaine totale du saut est NP-complet pour les graphes bipartites, et nous déterminons la valeur exacte de γhtR (G) pour les chemins et les cycles. De plus, nous caractérisons tous les graphes connectés G d'ordre n avecγhtR (G)∈{2,3,4,n}. Enfin, nous montrons que pour chaque arbre T de diamètre au moins 3, γhtR (T)≥ γht(T)+2, où γht (T) est le nombre de domination totale du houblon.Translated Description (Spanish)
En este artículo, iniciamos un estudio de la dominación romana total del salto definida de la siguiente manera: una función dominante romana total del salto (HTRDF) en un gráfico G=(V,E) es una función f:V→{0,1,2} tal que para cada vértice u con f(u) = 0 existe un vértice v a una distancia 2 de u con f(v) = 2 y el subgrafo inducido por los vértices asignados a valores distintos de cero bajo f no tiene vértices aislados. El peso de un HTRDF es la suma de los valores de su función en todos los vértices, y el número de dominación romana total del lúpulo γdtR (G) es igual al peso mínimo de un HTRDF en G. Proporcionamos varias propiedades en el número de dominación romana total del lúpulo. Más precisamente, mostramos que el problema de decisión correspondiente al problema de dominación romana total del lúpulo es NP-completo para gráficos bipartitos, y determinamos el valor exacto de γhtR(G) para rutas y ciclos. Además, caracterizamos todos los gráficos conectados G de orden n con γhtR(G)∈{2,3,4,n}. Finalmente, mostramos que para cada árbol T de diámetro al menos 3, γhtR (T)≥ γht (T)+2, donde γht (T) es el número de dominación total del lúpulo.Additional details
Additional titles
- Translated title (Arabic)
- هوب الهيمنة الرومانية الكلية في الرسوم البيانية
- Translated title (French)
- Sauter la domination romaine totale dans les graphiques
- Translated title (Spanish)
- Saltar a la dominación romana total en gráficos
Identifiers
- Other
- https://openalex.org/W4361278763
- DOI
- 10.1080/09728600.2023.2184288
References
- https://openalex.org/W1984228559
- https://openalex.org/W2618144827