查看更多>>摘要：A general position set of a graph G is a set of vertices S in G such that no three vertices from S lie on a common shortest path. In this paper we introduce and study the general position achievement game. The game is played on a graph G by players A and B who alternatively pick vertices of G. A selection of a vertex is legal if has not been selected before and the set of vertices selected so far forms a general position set of G. The player who selects the last vertex wins the game. Playable vertices at each step of the game are described, and sufficient conditions for each of the players to win is given. The game is studied on Cartesian and lexicographic products. Among other results it is proved that A wins the game on K-n square K-m if and only if both n and m are odd, and that B wins the game on G o K-n if and only if either B wins on G or n is even. (C) 2022 The Author(s). Published by Elsevier B.V.
查看更多>>摘要：We extend the Grundy number and the ochromatic number, parameters on graph colorings, to digraph colorings, we call them digrundy number and diochromatic number, respectively. First, we prove that for every digraph the diochromatic number equals the digrundy number (as happens for graphs). Then, we prove the interpolation property and the Nordhaus-Gaddum relations for the digrundy number, and improve the Nordhaus-Gaddum relations for the dichromatic and diachromatic numbers bounded previously by the authors in Araujo-Pardo et al. (2018). (C) 2022 Published by Elsevier B.V.
查看更多>>摘要：If for every two maximum independent sets A and B in a graph G there exists an automorphism of G that maps A to B, then we call G an alpha-iso-unique graph. We extend several known characterizations of trees that have a unique maximum independent set obtaining characterizations of alpha-iso-unique trees. Such trees either have the property that the deletion of any edge does not affect the independence number, or they have the central edge, which connects two isomorphic subtrees, and only the deletion of the central edge increases the independence number. One of the characterizations results in a linear time algorithm to recognize whether a given tree is alpha-iso-unique. In contrast, we prove that the problem of recognizing whether an arbitrary graph is alpha-iso-unique is not polynomial unless P = NP. Constructions of large families of alpha-iso-unique graphs are given involving simplicial vertices and chordal graphs. In particular, we show that every graph is an induced subgraph of an alpha-iso-unique graph. Finally, alpha-iso-unique graphs are characterized among Cartesian products G rectangle H of co-prime graphs G and H such that alpha(G rectangle H) = alpha(H)vertical bar V(G)vertical bar. (C) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：In this paper, we show that every (3k - 3)-edge-connected graph G, under a certain degree condition, can be edge-decomposed into k factors G(1), ..., G(k) such that for each vertex v is an element of V(G(i)), vertical bar dG(i)(v)- d(G)(v)/k vertical bar < 1, where 1 <= i <= k. As an application, we deduce that every 6-edge-connected graph G can be edge-decomposed into three factors G(1), G(2), and G(3) such that for each vertex v is an element of V(G(i))(3) with 1 <= i <= 3, vertical bar dG(i)(v) - d(G)(v)/3 vertical bar < 1, unless 3 G has exactly one vertex z with d(G)(z) (sic) 0. Next, we show that every odd-(3k - 2)-edge connected graph G can be edge-decomposed into k factors G(1), ..., G(k) such that for each vertex v is an element of V(G(i)), d(Gi)(v) and d(G) (v) have the same parity and vertical bar d(Gi)(v) - dG(v)/k vertical bar < 2, where k is an odd positive integer and 1 <= i <= k. Finally, we give a sufficient edge-connectivity condition for a graph G to have a parity factor F with specified odd-degree vertices such that for each vertex v, vertical bar d(F)(v) - epsilon d(G)(v)vertical bar < 2, where s is a real number with 0 < s < 1. (C) 2022 Elsevier B.V. All rights reserved.
NSTL
Elsevier