In this work, we study the -chromatic number of a graph, which is the chromatic number of the -complement of a graph. We give a structure of the -complements and sharp bounds on the -chromatic numbers of the Cartesian products of graphs. Furthermore, we compute the -chromatic numbers of various classes of Cartesian product graphs, including the Cartesian products among cycles, paths, and stars.
17 February 2022 in Transactions of the American Mathematical Society, Series B
Using the Birman exact sequence for pure mapping class groups, we construct a universal Cannon-Thurston map onto the boundary of a curve complex for a surface with punctures we call surviving curve complex. Along the way we prove hyperbolicity of this complex and identify its boundary as a space of laminations. As a corollary we obtain a universal Cannon-Thurston map to the boundary of the ordinary curve complex, extending earlier work of the second author with Mj and Schleimer [Comment. Math. Helv. 86 (2011), pp. 769–816].
This study examines the δ-complements of graphs—a specific type of graph complement whose adjacency depends on the adjacency of the vertices with identical degrees in the original graph. More specifically, we study this type of complement regarding the domination number. We provide sharp Nordhaus-Gaddum-type bounds on the domination number of a graph and its δ-complement. We also provide sharp bounds on the domination numbers of the δ-complements of joined graphs and Cartesian product graphs.
Let $ G $ be a connected graph of order $ n $. The representation of a vertex $ v $ of $ G $ with respect to an ordered set $ W = \{w_1, w_2, ..., w_k\} $ is the $ k $-vector $ r(v|W) = (d(v, w_1), d(v, w_2), ..., d(v, w_k)) $, where $ d(v, w_i) $ represents the distance between vertices $ v $ and $ w_i $ for $ 1\leq i\leq k $. An ordered set $ W $ is called a connected local resolving set of $ G $ if distinct adjacent vertices have distinct representations with respect to $ W $, and the subgraph $ \langle W\rangle $ induced by $ W $ is connected. A connected local resolving set of $ G $ of minimum cardinality is a connected local basis of $ G $, and this cardinality is the connected local dimension $ \mathop{\text{cld}}(G) $ of $ G $. Two vertices $ u $ and $ v $ of $ G $ are true twins if $ N[u] = N[v] $. In this paper, we establish a fundamental property of a connected local basis of a connected graph $ G $. We analyze the connected local dimension of a connected graph without a singleton true twin class and explore cases involving singleton true twin classes. Our investigation reveals that a graph of order $ n $ contains at most two non-singleton true twin classes when $ \mathop{\text{cld}}(G) = n-2 $. Essentially, our work contributes to the characterization of graphs with a connected local dimension of $ n-2 $.
3 May 2022 in AKCE International Journal of Graphs and Combinatorics
Let G be a connected graph and let v be a vertex of G. The representation of v with respect to an ordered set is the k-vector where is a distance between v and wi for If the representations of any two adjacent vertices of G with respect to W are distinct and the induced subgraph is connected, then W is called a connected local resolving set of G. The minimum cardinality of connected local resolving sets of G is referred to as the connected local dimension of G, denoted by A connected local resolving set of cardinality is called a minimum connected local resolving set or a connected local basis of G. The true twin graph tG of G is obtained by true twin equivalence classes of G such that the vertex set of tG consists of every true twin equivalence class of G and any two distinct vertices of tG are adjacent if the distance of them in G is 1. A connected local resolving set of tG containing all marked vertices is called a marked set of tG. A marked set of tG having minimum cardinality is called a minimum marked set or a marked basis of tG and this cardinality is called the marked dimension of tG, which is denoted by In this work, we investigate the connected local dimension of G by using the marked dimension of its true twin graph tG. The bounds for the connected local dimension of G are presented in terms of the marked dimension of tG and the clique number of a set of all marked vertices of tG.
In this work, we study the $δ$-chromatic number of a graph which is the chromatic number of the $δ$-complement of a graph. We give a structure of the $δ$-complements and sharp bounds on the $δ$-chromatic numbers of the Cartesian products of graphs. Furthermore, we compute the $δ$-chromatic numbers of various classes of Cartesian product graphs, including the Cartesian products between cycles, paths, and stars.