Search the digital library catalog

Abstract: An L(d,1)-labeling of a graph G=(V,E) is a function f from the vertex set V(G) to the set of nonnegative integers such that the labels on adjacent vertices differ by at least d and the labels on vertices at distance two differ by at least one, where d≥1. The span of f is the difference between the largest and the smallest numbers in f(V). The λ1d-number of G, denoted by λ1d(G), is the minimum span over all L(d,1)-labelings of G. We prove that λ1d(X)≤2d+2, with equality if 1≤d≤4, for direct graph bundle X=Cm×σℓCn and Cartesian graph bundle X=Cm□σℓCn, if certain conditions are imposed on the lengths of the cycles and on the cyclic ℓ-shift σℓ.
Keywords: L(d, 1)-labeling, λ d 1 -number, direct product of graph, direct graph bundle, Cartesian product of graph, Cartesian graph bundle, cyclic ℓ-shift, channel assignment
Published in DKUM: 13.03.2025; Views: 0; Downloads: 0
Full text (338,54 KB)
This document has many files! More...

Abstract: The general position number gp(G) of a connected graph G is the cardinality of a largest set S of vertices such that no three distinct vertices from S lie on a common geodesic; such sets are refereed to as gp-sets of G. The general position number of cylinders Pr ◻ Cs is deduced. It is proved that (Cr ◻ Cs)∈{6,7} whenever r ≥ s ≥ 3, s ≠ 4, and r ≥ 6. A probabilistic lower bound on the general position number of Cartesian graph powers is achieved. Along the way a formula for the number of gp-sets in Pr ◻ Ps, where r,s ≥ 2, is also determined.
Keywords: general position problem, Cartesian product of graphs, paths and cycles, probabilistic constructions, exact enumeration
Published in DKUM: 27.08.2024; Views: 39; Downloads: 7
Full text (586,20 KB)
This document has many files! More...

Abstract: We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing's conjecture. The new framework unifies two different approaches to the conjecture. The most common approach restricts one of the factors of the product to some class of graphs and proves the inequality of the conjecture then holds when the other factor is any graph. The other approach utilizes the so-called Clark-Suen partition for proving a weaker inequality that holds for all pairs of graphs. We demonstrate the strength of our framework by improving the bound of Clark and Suen as follows: ɣ(X◻Y) ≥ max{1/2ɣ(X) ɣt(Y), 1/2ɣt(X) ɣ(Y)}, where ɣ stands for the domination number, ɣt is the total domination number, and X◻Y is the Cartesian product of graphs X and Y.
Keywords: Cartesian product, total domination, Vizing's conjecture, Clark and Suen bound
Published in DKUM: 09.08.2024; Views: 86; Downloads: 9
Full text (179,75 KB)
This document has many files! More...

Abstract: Szeged-like topological indices are well-studied distance-based molecular descriptors, which include, for example, the (edge-)Szeged index, the (edge-)Mostar index, and the (vertex-)PI index. For these indices, the corresponding polynomials were also defined, i.e., the (edge-)Szeged polynomial, the Mostar polynomial, the PI polynomial, etc. It is well known that, by evaluating the first derivative of such a polynomial at x = 1, we obtain the related topological index. The aim of this paper is to introduce and investigate a new graph polynomial of two variables, which is called the SMP polynomial, such that all three vertex versions of the above-mentioned indices can be easily calculated using this polynomial. Moreover, we also define the edge-SMP polynomial, which is the edge version of the SMP polynomial. Various properties of the new polynomials are studied on some basic families of graphs, extremal problems are considered, and several open problems are stated. Then, we focus on the Cartesian product, and we show how the (edge-)SMP polynomial of the Cartesian product of n graphs can be calculated using the (weighted) SMP polynomials of its factors.
Keywords: SMP polynomial, edge-SMP polynomial, Cartesian product, Szeged index, Mostar index, PI index
Published in DKUM: 09.02.2024; Views: 262; Downloads: 29
Full text (320,27 KB)
This document has many files! More...

Abstract: Let γ(D) denote the domination number of a digraph D and let C$_m$□C$_n$ denote the Cartesian product of C$_m$ and C$_n$, the directed cycles of length n ≥ m ≥ 3. Liu et al. obtained the exact values of γ(C$_m$□C$_n$) for m up to 6 [Domination number of Cartesian products of directed cycles, Inform. Process. Lett. 111 (2010) 36–39]. Shao et al. determined the exact values of γ(C$_m$□C$_n$) for m = 6, 7 [On the domination number of Cartesian product of two directed cycles, Journal of Applied Mathematics, Volume 2013, Article ID 619695]. Mollard obtained the exact values of γ(C$_m$□C$_n$) for m = 3k + 2 [M. Mollard, On domination of Cartesian product of directed cycles: Results for certain equivalence classes of lengths, Discuss. Math. Graph Theory 33(2) (2013) 387–394.]. In this paper, we extend the current known results on C$_m$□C$_n$ with m up to 21. Moreover, the exact values of γ(C$_n$□C$_n$) with n up to 31 are determined.
Keywords: domination number, Cartesian product, directed cycle
Published in DKUM: 02.09.2022; Views: 611; Downloads: 13
Link to full text