2025-10-31
Meysam Korivand, Nasrin Soltankhah, Kazem Khashyarmanesh
A proper vertex-coloring of a graph G is called distinguishing, if the only automorphism preserving the colors is the identity. The minimum number of colors for such a coloring is denoted by χ D (G) . We say a graph G is uniquely proper distinguishing colorable (UPDC, for short) if and only if there exists only one partition of V(G) into χ D (G) independent sets such that the identity is the only automorphism of G preserving the partition. In this paper, we study the UPDC graphs. We show that a disconnected graph is UPDC if and only if it is the union of two isomorphic asymmetric connected bipartite graphs. We prove some results on bipartite UPDC graphs and show that any UPDC tree is one of the following: (i) an asymmetric tree, (ii) a tree with precisely one non-trivial automorphism and center xy such that this automorphism interchanges x and y , (iii) a star graph. Additional, a characterization of all graphs G of order n with the property that χ D (G∪G) = χ D (G) = k , where k=n-2, n-1, n , is given in this paper. Finally, we determine all graphs G of order n with the property that χ D (G∪G) = χ D (G)+1 = ℓ , where ℓ=n-1, n, n+1 .
2025-10-28
Khalid Kamyab, Mohsen Ghasemi, Rezvan Varmazyar
Suppose that G is minimally 4-restricted edge connected graph without triangle, δ(G) ≥ 2 and α 4 (G) ≥ 6 . Suppose that A is a λ 4 -atom of G such that for each path of length 3 in A , say P 3 = xyz , we have d A (y) − 1 = d A−{x,y,z} (y) , where x ∼ y ∼ z . In this paper, under these assumptions, we show that all atoms of G are trivial.
2025-10-28
Julia Ingrid Hoepner, Gary MacGillivray, Christina Mynhardt
A broadcast on a connected graph G is a function f : V ( G )→{0, 1, ..., d i a m ( G )} such that f ( v )≤ e ( v ) (the eccentricity of v ) for all v ∈ V . If d G ( u , v )≥ f ( u )+ f ( v ) for any pair of vertices u , v with f ( u )>0 and f ( v )>0 , the broadcast is said to be boundary independent. We show that the maximum weight α b n ( G ) of a boundary independent broadcast can be bounded in terms of the independence number α ( G ) , and prove that the maximum boundary independent broadcast problem is NP-hard. We investigate bounds on α b n ( T ) when T is a tree in terms of its order and the number of vertices of degree at least 3, and determine a sharp upper bound on α b n ( T ) when T is a caterpillar, giving α b n ( T ) exactly for certain families of caterpillars. We conclude by describing a polynomial-time algorithm to determine α b n ( T ) for a given tree T .
2025-10-28
Asmiati Asmiati, Kasandra Prawinasti, Maharani Damayanti, Lyra Yulianti
The locating chromatic number remains an active topic in graph theory. It combines the concepts of partition dimension and proper vertex coloring. A necessary condition for determining the locating chromatic number is that each vertex must have a unique color code under a minimal coloring. This paper investigates the locating chromatic number of the (k,n) -split cycle graph and its barbell operation.
2025-10-28
Kijung Kim
An Italian dominating function on a digraph D with vertex set V(D) is defined as a function f : V(D) → {0, 1, 2} such that every vertex v ∈ V(D) with f(v) = 0 has at least two in-neighbors assigned 1 under f or one in-neighbor w with f(w) = 2 . The weight of an Italian dominating function f is the value ω(f) = f(V(D)) = ∑ u∈V(D) f(u) . The Italian domination number of a digraph D , denoted by γ I (D) , is the minimum taken over the weights of all Italian dominating functions on D . The Italian bondage number of a digraph D , denoted by b I (D) , is the minimum number of arcs of A(D) whose removal in D results in a digraph D′ with γ I (D′) > γ I (D) . The Italian reinforcement number of a digraph D , denoted by r I (D) , is the minimum number of extra arcs whose addition to D results in a digraph D′ with γ I (D′) < γ I (D) . In this paper, we initiate the study of Italian bondage and reinforcement numbers in digraphs and present some bounds for b I (D) and r I (D) . We also determine the Italian bondage and reinforcement numbers of some classes of digraphs.
2025-10-28
Afeefa Maryam, M. Tariq Rahim, Fawad Hussain
The Radenković and Gutman conjecture establishes a relationship between the Laplacian energies of any tree T n , the star graph S n and the path graph P n , i.e., LE(P n ) ≤ LE(T n ) ≤ LE(S n ) . In this paper, we focus on verifying the validity of this conjecture for some classes of trees with diameter 5. By analyzing their structural properties and the corresponding Laplacian spectra, we establish that the conjecture holds for these few subclasses.
2025-10-28
Smruti Mane, Neeta Shinde
An important question in the study of quasi-perfect codes is whether such codes can be constructed for all possible lengths n . In this paper, we address this question for specific values of n . First, we investigate the existence of quasi-perfect codes in the Cartesian product of a graph G and a path (or cycle), assuming that G admits a perfect code. Second, we explore quasi-perfect codes in the Cartesian products of two or three cycles, C m □C n and C m □C n □C l , as well as in the Cartesian products of two or three paths, P m □P n and P m □P n □P l .