Given an oriented graph $\vec{G}$ and a subset of vertices $X \subseteq V(\vec{G})$, the \emph{inversion} of $X$ is the operation that reverses the orientation of every arc with both endpoints in $X$. For a simple graph $G$, the inversion diameter $\operatorname{diam}(I(G))$ is the maximum distance between two orientations of $G$ under inversions of vertex sets. We prove the sharp bound \[ \operatorname{diam}(I(G))\le 2\chi_a(G)-2, \] where $\chi_a(G)$ is the acyclic chromatic number. Consequently, every planar graph has inversion diameter at most $8$, improving the previously known bound $12$. Using strong-degeneracy arguments, we also obtain upper bounds $7$, $5$, and $4$ for planar graphs of girth at least $4$, $5$, and $6$, respectively.
The oriented diameter of a connected bridgeless graph $G$, denoted by $\overrightarrow{\operatorname{diam}}(G)$, is the minimum diameter among all strong orientations of $G$. We study the oriented diameter of planar triangulations, and show that $\overrightarrow{\operatorname{diam}}(G)\leq \frac{2n+44}{5}$ for any $n$-...
Let $G$ be a graph together with a total order $\prec$ on its edges. We say that $\prec$ is realizable in $\mathbb{R}^d$ if there is a placement of the vertices of $G$ in $\mathbb{R}^d$ such that the Euclidean lengths of the edges induce exactly the order $\prec$. Almendra-Hern\'andez and Mart\'inez-Sandoval proved tha...
Gerardo L. Maldonado, Leonardo Martínez-Sandoval, Miguel Raggi et al.· 0 citations
For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put \[ I_G(\sigma)=|E(G)\cap E(\sigma(G))|. \] Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In 1977 Erd\H{o}s...
For a planar graph $G = (V, E)$ embedded in $\mathbb{R}^2$, let $\mathcal{F}(G)$ denote the set of faces of $G$. Then $G$ is called a \textit{$C_n$-face-magic} graph if there exists a bijection $f: V(G) \to \{1, 2, \dots, |V(G)|\}$ such that for any $F \in \mathcal{F}(G)$ with $F \cong C_n$, the sum of all the vertex l...
P. Chalise, Richard M. Low, Arman Eisenkolb-Vaithyanathan· 0 citations
A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let $q_B(G)$ be the minimum number of colors in such a coloring. Every graph of maximum degree $\Delta$ is $K_{2,\Delta+1}$-free; hence the known $2\Delta$ bound for planar graphs with $\Delta\ge38$ (Kong et al...
Given a simple graph $G=(V,E)$ of order $p$ and size $q$, a bijection $f : V\cup E \to \{1, 2, \ldots, p+q\}$ is a local total neighborhood antimagic labeling of $G$ if the induced vertex coloring has the property $f^+_{tn}(u) \ne f^+_{tn}(v)$ for every two adjacent vertices $u$ and $v$ where $f^+_{tn}(u) = \sum (f(ux)...
Gee-choon Lau, W. Shiu, Zhen-Bin Gao· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
