查看更多>>摘要：An integer distance digraph is the Cayley graph Gamma(Z, S) of the additive group Z of all integers with respect to a finite subset S subset of Z. The domination ratio of Gamma(Z, S), defined as the minimum density of its dominating sets, is related to some number theory problems, such as tiling the integers and finding the maximum density of a set of integers with missing differences. We precisely determine the domination ratio of the integer distance graph Gamma(Z, {1, 2, ..., d -2, s}) for any integers d and s satisfying d >= 2 and s is not an element of [0, d-2]. Our result generalizes a previous result on the domination ratio of the graph Gamma(Z, {1, s}) with s is an element of Z \{0, 1} and also implies the domination number of certain circulant graphs Gamma(Z(n), S), where Z(n) is the finite cyclic group of integers modulo n and S is a subset of Z(n). (C) 2022 Elsevier B.V. All rights reserved.
Herrman, Rebekahvan Hintum, PeterSmith, Stephen G. Z.
8页
查看更多>>摘要：In this paper, we consider a variant of the cops and robbers game on a graph, introduced by Kinnersley and Peterson, in which every time the robber uses an edge, it is removed from the graph, known as bridge-burning cops and robbers. In particular, we study the maximum time it takes the cops to capture the robber. (C) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：Given a graph G = (V, E) with vertex set V and edge set E, we extend the concept of k-matching number and Hosoya index to a weighted graph (G; omega), where omega is a weight function defined over E. In particular, if phi is a vertex-degree-based (VDB) topological index defined via phi = phi(G) = Sigma(uv is an element of E) phi d(G)(u),d(G)(v), where d(G)(u) is the degree of the vertex u and phi(i,j) is an appropriate function with the property phi(i,j) = phi(j,i), then we consider the weighted graph (G; phi) with weight function phi : E -> R defined as phi(uv) = phi d(G)(u),d(G)(v), for all uv is an element of E. It turns out that m((G; phi), 1), the number of weighted 1-matchings in (G; phi), is precisely phi(G), and for k >= 2, the k-matching numbers m((G; phi), k) can be viewed as new kth order VDB-Hosoya indices. Later, we consider the extremal value problem of the Hosoya index over the set {T-n; phi} = {(T; phi) : T is an element of T-n}, where T-n is the set of trees with n vertices. (C) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：We develop a general theory of random walks on hypergraphs which includes, as special cases, the different models that are found in literature. In particular, we introduce and analyze general random walk Laplacians for hypergraphs, and we compare them to hypergraph normalized Laplacians that are not necessarily related to random walks, but which are motivated by biological and chemical networks. We show that, although these two classes of Laplacians coincide in the case of graphs, they appear to have important conceptual differences in the general case. We study the spectral properties of both classes, as well as their applications to Coupled Hypergraph Maps: discrete-time dynamical systems that generalize the well-known Coupled Map Lattices on graphs. Our results also show why for some hypergraph Laplacian variants one expects more classical results from (weighted) graphs to generalize directly, while these results must fail for other hypergraph Laplacians. (C) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：Nash-Williams proved that every graph has a well-balanced orientation. A key ingredient in his proof is admissible odd-vertex pairings. We show that for two slightly different definitions of admissible odd-vertex pairings, deciding whether a given odd-vertex pairing is admissible is co-NP-complete. This resolves a question of Frank. We also show that deciding whether a given graph has an orientation that satisfies arbitrary local arc-connectivity requirements is NP-complete. (C) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：An even cycle decomposition of an Eulerian graph is a partition of the edge set into even cycles. We color the even cycles so as two cycles sharing at least one vertex receive distinct colors. If k is the minimum number of required colors in such a coloring, then the even cycle decomposition has index k. We prove that the line graph of every bridgeless cubic graph of oddness 2 has an even cycle decomposition of index 3. The same property holds for the line graphs of some infinite families of class 2 cubic graphs with arbitrary large oddness. The construction of even cycle decompositions of index 3 in the line graph of a class 2 cubic graph is alternative to the constructions that are known in the literature; that one for the line graph of a cubic graph with arbitrary large oddness is also a new contribution to the more general problem on the existence of even cycle decompositions in the line graph of a bridgeless cubic graph. The constructions are obtained by applying a novel coloring technique on the edges of the line graph. (c) 2022 Elsevier B.V.
查看更多>>摘要：The eccentric distance sum and degree distance have been well-studied in the past several years. More recently, many authors have considered the relationships between several distance-based graph invariants. Hua et al. (2018) investigated the relationship between the eccentric distance sum and the degree distance. In this paper, we present upper and lower bounds on ??d(G) ??? D???(G) among all connected graphs. The sharp lower and upper bounds on ??d(G)???D???(G) of general graphs with given connectivity (resp. edge number, number of cut edges, and matching number) are determined. In addition, we characterize the extremal graphs attaining those bounds. ?? 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：The Turan number of a graph H, denoted by ex(n, H), is the maximum number of edges in an n-vertex graph that does not have H as a subgraph. Let TPk be the triangular pyramid of k-layers. In this paper, we determine that ex(n, TP3) = 1/4n(2) + n + o(n) and pose a conjecture for ex(n, TP4). (C) 2022 Published by Elsevier B.V.
Cheon, Gi-SangChoi, Hong JoonEsteban, GuillermoSong, Minho...
15页
查看更多>>摘要：By using the Riordan array method together with combinatorial species theory, we study enumeration problems for geometric graphs which are connected bipartite non-crossing graphs with n + 1 points in convex position. It is performed from two different points of view, one is by the distance between two vertices 1 and n + 1, and the other one is by the degree of the vertex n + 1. As a result, we obtain a production matrix for such geometric graphs, and a formula for the number of connected bipartite graphs, which gives an answer to an open question about the connected bipartite non-crossing graphs. ?? 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：Given a graph G, let f(G)(n, m) be the minimal number k such that every k independent n-sets in G have a rainbow m-set. Let D(2) be the family of all graphs with maximum degree at most two. For t >= 3, let C-t be the cycle with vertex set [1, t] and edge set {12, 23, ..., (t - 1)t, t1}. Aharoni et al. (2019) conjectured that (i) f(G)(n, n-1) = n - 1 for all graphs G is an element of D(2) and (ii) f(Ct)(n, n) = n for t >= 2n + 1. Lv and Lu (2020) showed that the conjecture (ii) holds when t = 2n + 1. In this article, we show that the conjecture (ii) holds for t >= 1/3n(2) + 44/9n. An ordered set I = (a(1), a(2), , a(n)) on C-t is called a 2-jump independent n-set of C-t if a(i+1) a(i) = 2 (mod t) for any 1 <= i <= n - 1. We also show that a collection of 2-jump independent n-sets F of C-t with vertical bar F vertical bar = n admits a rainbow independent n-set, i.e. (ii) holds if we restrict F on the family of 2-jump independent n-sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds for all graphs G is an element of D(2) with ce(()G) <= 4, where c(e)(G) is the number of components of G isomorphic to cycles of even lengths. (C) 2022 Elsevier B.V. All rights reserved.
NSTL
Elsevier