查看更多>>摘要：A b-coloring of a graph is a proper coloring of its vertices such that each color class contains a vertex adjacent to at least one vertex of every other color class. The b-chromatic number of a graph is the largest integer k such that the graph has a b-coloring with k colors. In this work we present lower bounds for the b-chromatic number of a vertex-deleted subgraph of a graph, particularly regarding two important classes, claw-free graphs and chordal graphs. We also get bounds for the b-chromatic number of G - {x}, when G is a graph with large girth. (C) 2021 Published by Elsevier B.V.
查看更多>>摘要：In this paper we study the preference-based activity scheduling problem, where based on preference sets of participants, activities need to be scheduled in parallel, such that participants can attend as many of their preferred activities as possible. The Activity Scheduling Problem (ASP) takes as input the activities, time slots, participants and their set of preferences, and is supposed to output an optimal schedule. Attendance is the number of preferred activities a participant can attend. We present two lower bounds on the average attendance over all participants, based on linearity of expectation. The first is a bound that involves the different parameters of ASP; we prove that this bound is tight. The second bound is such that no matter how many activities, participants, and time slots are included in the event, there is always a schedule that guarantees an average attendance of (1 - 1/e) of the preferred activities for the participants. A further result, based on applying the Lovasz local lemma to hypergraph coloring, presents a lower bound on the minimum attendance over all participants. We show that for various values of the problem's parameters this bound is better than a simple bound, although the simple bound may be tight for instances with a very large number of participants. (C) 2021 Elsevier B.V. All rights reserved.
Ma, FuhongMasarik, TomasChoi, IlkyooClemen, Felix Christian...
13页
查看更多>>摘要：A graph where each vertex v has a list L(v) of available colors is L-colorable if there is a proper coloring such that the color of v is in L(v) for each v. A graph is k-choosable if every assignment L of at least k colors to each vertex guarantees an L-coloring. Given a list assignment L, an L-request for a vertex v is a color c is an element of L(v). In this paper, we look at a variant of the widely studied class of precoloring extension problems from Dvorak, Norin, and Postle (J. Graph Theory, 2019), wherein one must satisfy "enough'', as opposed to all, of the requested set of precolors. A graph G is epsilon-flexible for list size k if for any k-list assignment L, and any set S of L-requests, there is an L-coloring of G satisfying epsilon-fraction of the requests in S. It is conjectured that planar graphs are epsilon-flexible for list size 5, yet it is proved only for list size 6 and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masarik and show that planar graphs without K-4(-) are epsilon-flexible for list size 5. We also prove that planar graphs without 4-cycles and 3-cycle distance at least 2 are epsilon-flexible for list size 4. Finally, we introduce a new (slightly weaker) form of epsilon-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are epsilon-flexible for list size 5. (C) 2021 The Author(s). Published by Elsevier B.V.
查看更多>>摘要：Let G = (V, E) be a connected graph. H denotes a family of pairwise disjoint graphs {H-v}(v is an element of V). The Zykov sum of G and H, denoted by G[H], is the graph obtained from G by replacing every vertex v of G with graph H-v and all vertices of H-u, H-v are adjacent if uv is an element of E. In this paper, we first give a decomposition formula for the independence polynomial I (G[H]; x). Then, we derive a formula expressing the Fibonacci number of G[H] in terms of the independence polynomial of graph G and the Fibonacci number of H-v. Finally, as applications, we compute the independence polynomials and the Fibonacci numbers of several interesting graphs, such as the windmill graphs, the path network and the ring network. (C) 2021 Elsevier B.V. All rights reserved.
查看更多>>摘要：Recently it was shown that a certain class of phylogenetic networks, called level-2 networks, cannot be reconstructed from their associated distance matrices. In this paper, we show that they can be reconstructed from their induced shortest and longest distance matrices. That is, if two level-2 networks induce the same shortest and longest distance matrices, then they must be isomorphic. We further show that level-2 networks are reconstructible from their shortest distance matrices if and only if they do not contain a subgraph from a family of graphs. A generator of a network is the graph obtained by deleting all pendant subtrees and suppressing degree-2 vertices. We also show that networks with a leaf on every generator side are reconstructible from their induced shortest distance matrix. (C) 2021 The Author(s). Published by Elsevier B.V.
查看更多>>摘要：In this paper we study lower bounds in a unified way for a large family of topological indices, including the first variable Zagreb index M-1(alpha). Our aim is to obtain sharp inequalities and characterize the corresponding extremal graphs. The main results provide lower bounds for several vertex-degree-based topological indices. These bounds are new even for the first Zagreb, the inverse and the forgotten indices. (C) 2021 Elsevier B.V. All rights reserved.
查看更多>>摘要：Let G = (V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). The line graph L-G of G is the graph with E(G) as its vertex set and two vertices of L-G are adjacent in L-G if and only if they have a common end-vertex in G. The resistance distance R-G(x, y) between two vertices x, y of G is equal to the effective resistance between the two vertices in the corresponding electrical network in which each edge of G is replaced by a unit resistor. The resistance diameter D-r(G) of G is the maximum resistance distance among all pairs of vertices of G. In this paper, it was shown that the resistance diameter of the line graph of a tree or unicyclic graph is no more than that of its initial graph by utilizing series and parallel principles, the principle of elimination and star-mesh transformation in electrical network theory. And experiment also indicated that the inequality D-r(L-G) <= D-r(G) is true for every simple nonempty connected graph G with less than 12 vertices. Thus it was conjectured that D-r(L-G) <= D-r(G) for every simple nonempty connected graph G. (C) 2021 Elsevier B.V. All rights reserved.
NSTL
Elsevier