查看更多>>摘要：The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to the graph. The extra edge can either be selected adversarially, in which case we are interested in the largest possible value that the MD can take, or uniformly at random, in which case we are interested in the distribution of the MD. The adversarial setting has already been studied by Eroh et al., (2015) for general graphs, who found an example where the MD doubles on adding a single edge. By constructing a different example, we show that this increase can be as large as exponential. However, we believe that such a large increase can occur only in specially constructed graphs, and that in most interesting graph families, the MD at most doubles on adding a single edge. We prove this for d-dimensional grid graphs, by showing that 2d appropriately chosen corners and the endpoints of the extra edge can distinguish every pair of nodes, no matter where the edge is added. For the special case of d = 2, we show that it suffices to choose the four corners as landmarks. Finally, when the extra edge is sampled uniformly at random, we conjecture that the MD of 2-dimensional grids converges in probability to 3 + Ber(8/27), and we give an almost complete proof. (C) 2022 The Author(s). Published by Elsevier B.V.
查看更多>>摘要：DP-coloring as a generalization of list coloring was introduced recently by Dvorak and Postle. The DP-chromatic number of G, denoted by chi(DP)(G), is the minimum number k such that G is DP - k-colorable. The variation of the Randic index R'(G) of a graph G is defined as the sum of the weights 1/max{d(u),d(v)} of all edges u(v) of G, where d(u) is the degree of the vertex u in G. In this paper, we show that for any graph G of order n, X-DP(G) <= 2R'(G), and this bound is sharp for all n and 2 <= chi(DP)(G) <= n. (C) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：We introduce the fractional version of oriented coloring and initiate its study. We prove some basic results and study the parameter for directed cycles and sparse planar graphs. In particular, we show that for every ?? > 0, there exists an integer g?? > 12 such that any oriented planar graph having girth at least g?? has fractional oriented chromatic number at most 4 + ??. Whereas, it is known that there exists an oriented planar graph having girth at least g?? with oriented chromatic number equal to 5. We also study the fractional oriented chromatic number of directed cycles and provide its exact value. Interestingly, the result depends on the prime divisors of the length of the directed cycle. ?? 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：A signed graph is a simple graph with two types of edges: positive and negative edges. Switching a vertex nu of a signed graph corresponds to changing the type of each edge incident to nu. A homomorphism from a signed graph G to another signed graph H is a mapping : phi : V(G) -> V(H) such that, after switching some of the vertices of G, phi maps every edge of G to an edge of H of the same type. The chromatic number chi(s)(G) of a signed graph G is the order of a smallest signed graph H such that there is a homomorphism from G to H. The maximum average degree mad(G) of a graph G is the maximum of the average degrees of all the subgraphs of G. We denote M-k the class of signed graphs with maximum average degree less than k and P-g the class of planar signed graphs of girth at least g. We prove: chi(s)(P7) <= 5, chi(s)(M-17/5) <= 10 which implies chi(s) (P-5) <= 10, chi(s)(M4-8/q+3) <= q + 1 with q a prime power congruent to 1 modulo 4. (C) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：Let G be a simple connected graph. For any two vertices u and v, let d(u, v) denote the distance between u and v in G. A radio-k-labeling of G for a fixed positive integer k is a function f which assigns to each vertex a non-negative integer label such that for every two vertices u and v in G, vertical bar f(u) -f(v)vertical bar >= k - d(u, v) + 1. The span of f is the difference between the largest and smallest labels of f(V). The radio-k-number of a graph G, denoted by rn(k)(G), is the smallest span among all radio-k-labelings admitted by G. A cycle C-n has diameter d = Left perpendicularn/2right perpendicular. In this paper, we combine a lower bound approach with cyclic group structure to determine the value of rn(k)(C-n) for k >= n - 3. For d <= k < n - 3, we obtain the values of rn(k)(C-n) when n and k have the same parity, and prove partial results when n and k have different parities. Our results extend the known values of rn(d)(C-n) and rn(d+1)(C-n) shown by Liu and Zhu (2005), and by Karst et al. (2017), respectively. (C) 2022 The Author(s). Published by Elsevier B.V.
查看更多>>摘要：We prove new non-existence results for vectorial monomial Dillon type bent functions mapping the field of order 2(2m) to the field of order 2(m/3). When m is odd and m > 3 we show that there are no such functions. When m is even we derive a condition for the bent coefficient. The latter result allows us to find examples of bent functions with m = 6 in a simple way. (C) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：Let G(k) denote the set of connected k-regular graphs G, k >= 2, where the number of vertices at distance 2 from any vertex in G does not exceed k. Asratian (2006) showed (using other terminology) that a graph G is an element of G(k) is Hamiltonian if for each vertex u of G the subgraph induced by the set of vertices at distance at most 2 from u is 2-connected. We prove here that in fact all graphs in the sets G(3), G(4) and G(5) are Hamiltonian. We also prove that the problem of determining whether there exists a Hamilton cycle in a graph from G(6) is NP-complete. Nevertheless we show that every locally connected graph G is an element of G(k), k >= 6, is Hamiltonian and that for each non-Hamiltonian cycle C in G there exists a cycle C' of length vertical bar V(C)vertical bar + l in G, l is an element of {1, 2}, such that V(C) subset of V(C'). Finally, we note that all our conditions for Hamiltonicity apply to infinitely many graphs with large diameters. (C) 2022 The Authors. Published by Elsevier B.V.
查看更多>>摘要：Let (G, .) be a finite group with the identity e and S a subset of G\{e} such that S = S-1. For t is an element of N and 2 <= t <= max{o(x) : x is an element of S}, the t-Cayley hypergraph of G over S is the hypergraph whose vertex set is G and edge set is {{yx(i) : 0 <= i <= t - 1} : x is an element of S and y is an element of G}. In this work, we study spectral properties of this hypergraph. We characterize integral 2-Cayley hypergraphs of G when G is abelian. In addition, we obtain the algebraic degree of t-Cayley hypergraphs of Z(n). (C) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：A finite word w is called rich if it contains vertical bar w vertical bar +1 distinct palindromic factors including the empty word. For every finite rich word w there are distinct nonempty palindromes w(1), w(2), ..., w(p) such that w = w(p)w(p-1) ... w(1) and w(i) is the longest palindromic suffix of w(p)w(p-1) ... w(i), where 1 <= i <= p. This palindromic factorization is called UPS-factorization. Let luf(w) = p be the length of UPS-factorization of w. In 2017, it was proved that there is a constant c such that if w is a finite rich word and n = vertical bar w vertical bar then luf(w) <= cn/ln n . We improve this result as follows: There are positive constants mu, kappa such that if w is a finite rich word and n = vertical bar w vertical bar then luf(w) <= mu/e(kappa)root ln n. The constants c, mu, kappa depend on the size of the alphabet. (C) 2022 Elsevier B.V. All rights reserved.
NSTL
Elsevier