Iskanje po katalogu digitalne knjižnice

Opis: Given a graph ▫$G$▫, the maximum size of an induced subgraph of ▫$G$▫ each component of which is a star is called the edge open packing number, ▫$\rho_{e}^{o} (G)$▫, of ▫$G$▫. Similarly, the maximum size of an induced subgraph of ▫$G$▫ each component of which is the star ▫$K_{1,1}$▫ is the induced matching number, ▫$\nu_I(G)$▫, of ▫$G$▫. While the inequality ▫$\rho_{e}^{o}(G)\ge \nu_I(G)$▫ clearly holds for all graphs ▫$G$▫, we provide a structural characterization of those trees that attain the equality. We prove that the induced matching number of the lexicographic product ▫$G\circ H$▫ of arbitrary two graphs ▫$G$▫ and ▫$H$▫ equals ▫$\alpha(G)\nu_I(H)$▫. By similar techniques, we prove sharp lower and upper bounds on the edge open packing number of the lexicographic product of graphs, which in particular lead to NP-hardness results in triangular graphs for both invariants studied in this paper. For the direct product ▫$G\times H$▫ of two graphs we provide lower bounds on ▫$\nu_I(G\times H)$▫ and ▫$\rho_{e}^{o} (G\times H)$▫, both of which are widely sharp. We also present sharp lower bounds for both invariants in the Cartesian and the strong product of two graphs. Finally, we consider the edge open packing number in hypercubes establishing the exact values of ▫$\rho_{e}^{o} (Q_n)$▫ when ▫$n$▫ is a power of ▫$2$▫, and present a closed formula for the induced matching number of the rooted product of arbitrary two graphs over an arbitrary root vertex.
Ključne besede: induced matching, edge open packing, graph product, independent set, trees
Objavljeno v DKUM: 25.07.2025; Ogledov: 0; Prenosov: 5
Celotno besedilo (1,31 MB)
Gradivo ima več datotek! Več...

Opis: 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 σℓ.
Ključne besede: 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
Objavljeno v DKUM: 13.03.2025; Ogledov: 0; Prenosov: 11
Celotno besedilo (338,54 KB)
Gradivo ima več datotek! Več...

Opis: A longest sequence (v1,....,vk) of vertices of a graph G is a Grundy total dominating sequence of G if for all i, N(vi)\U{j=1}^{i-1} N(vj)≠∅. The length k of the sequence is called the Grundy total domination number of G and denoted ɣ{gr}^{t}(G). In this paper, the Grundy total domination number is studied on four standard graph products. For the direct product we show that ɣ{gr}^{t}(G x H) > ɣ{gr}^{t}(G)ɣ{gr}^{t}(H), conjecture that the equality always holds, and prove the conjecture in several special cases. For the lexicographic product we express ɣ{gr}^{t}(G o H) in terms of related invariant of the factors and find some explicit formulas for it. For the strong product, lower bounds on ɣ{gr}^{t}(G ⊠ H) are proved as well as upper bounds for products of paths and cycles. For the Cartesian product we prove lower and upper bounds on the Grundy total domination number when factors are paths or cycles.
Ključne besede: total domination, Grundy total domination number, graph product
Objavljeno v DKUM: 07.08.2024; Ogledov: 96; Prenosov: 11
Celotno besedilo (248,02 KB)
Gradivo ima več datotek! Več...

Opis: The Wiener index of a connected graph ▫$G$▫ is the sum of distances between all pairs of vertices of ▫$G$▫. The strong product is one of the four most investigated graph products. In this paper the general formula for the Wiener index of the strong product of connected graphs is given. The formula can be simplified if both factors are graphs with the constant eccentricity. Consequently, closed formulas for the Wiener index of the strong product of a connected graph ▫$G$▫ with a cycle are derived.
Ključne besede: Wiener index, graph product, strong product
Objavljeno v DKUM: 30.11.2017; Ogledov: 1479; Prenosov: 447
Celotno besedilo (424,67 KB)
Gradivo ima več datotek! Več...

Opis: By Ulam's conjecture every finite graph ▫$G$▫ can be reconstructed from its deck of vertex deleted subgraphs. The conjecture is still open, but many special cases have been settled. In particular, one can reconstruct Cartesian products. We consider the case of ▫$k$▫-vertex deleted subgraphs of Cartesian products and prove that one can decide whether a graph ▫$H$▫ is a ▫$k$▫-vertex deleted subgraph of a Cartesian product ▫$G$▫ with at least ▫$k+1$▫ prime factors on at least ▫$k+1$▫ vertices each, and that ▫$H$▫ uniquely determines ▫$G$▫. This extends previous works of the authors and Sims. This paper also contains a counterexample to a conjecture of MacAvaney.
Ključne besede: mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs
Objavljeno v DKUM: 31.03.2017; Ogledov: 1558; Prenosov: 611
Celotno besedilo (197,33 KB)
Gradivo ima več datotek! Več...