查看更多>>摘要：The Grundy and b-chromatic number of graphs are two important chromatic parameters. The Grundy number of a graph G, denoted by Gamma(G) is the worst case behavior of greedy (First-Fit) coloring procedure for G and the b-chromatic number b(G) is the maximum number of colors used in any color-dominating coloring of G. Because the nature of these colorings are different they have been studied widely but separately in the literature. In this paper we first prove that Gamma(G) - inverted right perpendicularlog Gamma(G)inverted right perpendicular <= b(G), if the girth of G is sufficiently large with respect to its maximum degree. Next, we prove that if G is K-2,K-3-free then Gamma(G) <= (b(G))(3)/2. These results confirm a previous conjecture for these families of graphs. (C) 2021 Elsevier B.V. All rights reserved.
查看更多>>摘要：We study the general Randic index R-a(G) = Sigma(uv is an element of E)((G) )[deg(G)(u)deg(G)(v)](a), where a is an element of R, E(G) is the edge set of a graph G, and deg(G)(u) and deg(G)(v) are the degrees of vertices u and v, respectively. For a set of unicyclic graphs of given order and diameter, we present the unique graph having the minimum general Randic index, where -0.64 <= a < 0. Since R-1/2(G) is the Randi6 index of a graph G, our result holds also for the classical Randic index. (C) 2021 Elsevier B.V. All rights reserved.
Georges, J. P.Kuenzel, K.Mauro, D. W.Skardal, P. S....
15页
查看更多>>摘要：Inspired by distance-constrained graph labelings that model the assignment of frequencies to transmitters, we introduce a distance-constrained labeling of connected graphs that models the assignment of frequencies to oscillators. For a graph G and a vector of nonnegative real numbers k = (k(1), k(2), ..., k(p)), an L*(G; k)-labeling is any function f from V(G) into R such that for each i, 1 <= i <= p, vertical bar f(v) - f(w)vertical bar <= k(i) if d(v, w) = i. The span off is the absolute difference between the supremum and infimum of the image of f , and lambda(G,K)*, is the maximum span over all L*(G, k) labelings. In this paper, we explore the properties of lambda(G,K)* as a function of k, including continuity. And, for p = 2, we establish lambda(G,K)* when G is either a tree or a cycle. (C) 2021 Elsevier B.V. All rights reserved.
Alameda, Joseph S.Kritschgau, JurgenWarnberg, NathanYoung, Michael...
14页
查看更多>>摘要：A leak is a vertex that is not allowed to perform a force during the zero forcing process. Leaky forcing was recently introduced as a new variation of zero forcing in order to analyze how leaks in a network disrupt the zero forcing process. The l-leaky forcing number of a graph is the size of the smallest zero forcing set that can force a graph despite l leaks. A graph G is l-resilient if its zero forcing number is the same as its l-leaky forcing number. In this paper, we analyze l-leaky forcing and show that if an (l - 1)-leaky forcing set B is robust enough, then B is an l-leaky forcing set. This provides the framework for characterizing l-leaky forcing sets. Furthermore, we consider structural implications of l-resilient graphs. We apply these results to bound the l-leaky forcing number of several graph families including trees, supertriangles, and grid graphs. In particular, we resolve a question posed by Dillman and Kenter concerning the upper bound on the 1-leaky forcing number of grid graphs. (C) 2021 Published by Elsevier B.V.
查看更多>>摘要：For a graph G, the signless Laplacian matrix Q(G) is defined as Q(G) = D(G)+A(G), where A(G) is the adjacency matrix of G and D(G) the diagonal matrix whose main entries are the degrees of the vertices in G. The Q-spectrum of G is that of Q(G). In the present paper, we are interested in the minimum values of the second largest signless Laplacian eigenvalue q(2)(G) of a connected graph G. We find the five smallest values of q(2)(G) over the set of connected graphs G with given order n. We also characterize the corresponding extremal graphs. (C) 2021 Elsevier B.V. All rights reserved.
查看更多>>摘要：Given a real number alpha is an element of (0,1), we define the Webster sequence of density alpha to be W-alpha=((inverted right perpendicular )(n-1/2)/alpha(inverted left perpendicular ))(n is an element of N), where (inverted right perpendicular) x (inverted left perpendicular ) is the ceiling function. It is known that if alpha and beta are irrational with alpha+beta=1, then W-alpha and W-beta partition N. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of N into sequences W-alpha,W-beta,W-gamma with alpha,beta,gamma irrational. In this paper, we consider the question of how close one can come to a three-part partition of N into Webster sequences with prescribed densities alpha,beta,gamma. We show that if alpha,beta,gamma are irrational with alpha+beta+gamma=1, there exists a partition of N into sequences of densities alpha,beta,gamma, in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the nth element of each sequence in O(1) time and the second algorithm gives the assignment of the mth positive integer to a sequence in O(1) time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems. (C) 2021 Elsevier B.V. All rights reserved.
查看更多>>摘要：This paper deals with constructing obstruction sets for two subclasses of 4-searchable graphs. We first characterize the 4-searchable biconnected outerplanar graphs by listing all graphs that cannot be their minors; we then give a constructive characterization of such graphs. We also characterize the 4-searchable biconnected generalized wheel graphs by listing all graphs that cannot be their minors. Crown Copyright (C) 2021 Published by Elsevier B.V. All rights reserved.
查看更多>>摘要：In this paper the problem of maximizing vertex-degree function index H-f(G) for trees and unicyclic graphs G of order n and independence number s is solved for strictly convex functions f (x). In the case of unicyclic graphs f(x) must also satisfy strict inequality f(4) + 3f(2) > 3f(3) +f(1). These conditions are fulfilled by general first Zagreb index R-0(alpha)(G) for alpha > 2, second multiplicative Zagreb index Pi(2)(G) and sum lordeg index SL(G). The extremal graphs are unique and they are stars or have diameter equal to three or to four. The same results are valid for the corresponding minimization problem when f(x) is strictly concave and the inequality is reversed. (C) 2021 Elsevier B.V. All rights reserved.
Jones, Atila A.Protti, FabioDel-Vecchio, Renata R.
9页
查看更多>>摘要：An edge clique partition of G is a set of edge-disjoint cliques of G which together contain every edge of G. In this work we investigate the computational complexity of determining the minimum size of an edge clique partition of G, denoted by cp(G). This problem is NP-hard for split graphs and K-4-free graphs. We establish a complete complexity classification of this problem on the hierarchy of (k, l)-graphs, graphs that can be partitioned into k independent sets and l complete sets. In addition, we determine in polynomial time the value of cp(G) for interesting subclasses of (k, l)-graphs: split-indifference graphs, partial 2-trees, and triangular grids. (C) 2021 Elsevier B.V. All rights reserved.
查看更多>>摘要：Let the k-uniform hypergraph Fan(k) consist of k edges that pairwise intersect exactly in one vertex x, plus one more edge intersecting each of these edges in a vertex different from x. Mubayi and Pikhurko (2007), determined the exact Turan number ex(n, Fan(k)) of Fan(k) for sufficiently large n, which provides a generalization of Mantel's theorem. In this paper, we give a sparse version of Mubayi and Pikhurko's result. For a fixed integer k (k >= 3), let G(k) (n, p) be a probability space consisting of k-uniform hypergraphs with n vertices, in which each element of (([n])(k)) occurring independently as an edge with probability p. We show that there exists a positive constant K such that with high probability the following is true. If p > K/n, then every maximum Fan(k)-free subhypergraph of G(k)(n, p) is k-partite for k >= 4; and if p > K(logn)(gamma)/n, where gamma > 0 is an absolute constant, then every maximum Fan(3)-free subhypergraph of G(3)(n, p) is tripartite. Our result is an exact version of a random analogue of the stability result of Fan(k)-free(k)-graphs, which can be obtained by using the transference theorem given by Samotij (2014). (C) 2021 Elsevier B.V. All rights reserved.
NSTL
Elsevier