Narrow Results

A new kind of bipartite graph is defined in this paper. The work is motivated mainly from a graph introduced by Al-Kaseasbeh and Erfanian [A bipartite graph associated to elements and cosets of subgroups of a finite group, AIMS Math. 6(10) (2021) 10395–10404] and partially from the undirected power graph of a group and from the inclusion graph. For a nontrivial group $G$, we define a simple undirected bipartite graph $\mathrm{\Gamma }(G)$ with the vertex set $V(\mathrm{\Gamma }(G))=A\cup B$, where $A$ is the set of all elements of the group $G$ and $B$ is the set of all subgroups $H$ of $G$ such that $H\ne \{e\}$ and two vertices $a\in A$ and $H\in B$ are adjacent if and only if $a^2\in H$. Here, we classify all the finite groups $G$ whose bipartite graphs $\mathrm{\Gamma }(G)$ are planar. In addition, we also classify the finite groups $G$ such that $\mathrm{\Gamma }(G)$ is outerplanar, maximal planar, maximal outerplanar, star, tree, claw graph, respectively. The planarity of the graph $\mathrm{\Gamma }(G)$ corresponding to an infinite group $G$ has also been investigated here. It is also observed that $\mathrm{\Gamma }(G)$ satisfies Vizing’s conjecture.

We investigate the computational complexity of the following problem. Given a planar graph in which some vertices have already been placed in the plane, place the remaining vertices to form a planar straight-line drawing of the whole graph. We show that this extensibility problem, proposed in the 2003 "Selected Open Problems in Graph Drawing" [1], is NP-hard.

We present au intuitive and simple O(log² n log Φ) time, O(n² M(n)) processor parallel algorithm for finding a perfect matching in a planar graph, where n is the order, Φ is the number of the distinct perfect matchings of the graph and M(n) is the best sequential complexity of matrix multiplication of size n. The algorithm runs on a CRCW PRAM. Clearly, our algorithm belongs to the class NC if the number of perfect matchings is polynomially bounded in the size of the input graph.

Planar networks are an important special class of networks that arise in several application contexts. Because of the special structure of planar networks, network flow algorithms often run faster on these networks than they do on more general networks. In first part (Secs. 2–5), we present an algorithm for finding maximum cut and an algorithm for finding minimum flow in directed $1-n$ planar static networks with arcs and nodes capacities. This part is presented in Ciurea et al. [Proc. 5th Int. Conf. Control Decision and Information Technologies (CoDIT2018), Thessaloniki, Greece (2018), pp. 110–115]. In the second part (Secs. 6–8), we present this problem in directed $1-n$ planar dynamic networks with arcs and nodes capacities.

A simultaneous embedding with fixed edges (SEFE) of a set of k planar graphs G₁,…,G_k on the same set of vertices is a set of k planar drawings of G₁,…,G_k, respectively, such that each vertex is placed on the same point in all the drawings and each edge is represented by the same Jordan curve in the drawings of all the graphs it belongs to. A simultaneous geometric embedding (SGE) is a SEFE in which the edges are represented by straight-line segments.

Given k planar graphs G₁,…,G_k, deciding whether they admit a SEFE and whether they admit an SGE are NP-hard problems, for k ≥ 3 and for k ≥ 2, respectively.

In this paper we consider the complexity of SEFE and of SGE when the graphs G₁,…,G_k have a fixed planar embedding.

In sharp contrast with the NP-hardness of SEFE for three non-embedded planar graphs, we show that SEFE is quadratic-time solvable for three graphs with a fixed planar embedding.

Furthermore, we show that, given k embedded planar graphs G₁,…,G_k, deciding whether a SEFE of G₁,…,G_k exists and deciding whether an SGE of G₁,…,G_k exists are NP-hard problems, for k ≥ 14 and k ≥ 13, respectively.

We present an algorithm for testing the inscribability of a trivalent polyhedron or, equivalently, testing the circumscribability of a simplicial polyhedron. Our algorithm, which runs in linear time and uses only low-precision integer arithmetic, is based on a purely combinatorial characterization of inscribable trivalent polyhedra.

We consider the problem of embedding the vertices of a plane graph into a small (polynomial size) grid in the plane in such a way that the edges are straight, nonintersecting line segments and faces are convex polygons. We present a linear-time algorithm which, given an n-vertex 3-connected plane G (with n ≥ 3), finds such a straight-line convex embedding of G into a (n - 2) × (n - 2) grid.

Hassler Whitney's theorem of 1931 reduces the task of finding proper, vertex 4-colorings of triangulations of the 2-sphere to finding such colorings for the class ℌ of triangulations of the 2-sphere that have a Hamiltonian circuit. This has been used by Whitney and others from 1936 to the present to find equivalent reformulations of the 4 Color Theorem (4CT). Recently there has been activity to try to use some of these reformulations to find a shorter proof of the 4CT. Every triangulation in ℌ has a dual graph that is a union of two binary trees with the same number of leaves. Elements of a group known as Thompson's group F are equivalence classes of pairs of binary trees with the same number of leaves. This paper explores this resemblance and finds that some recent reformulations of the 4CT are essentially attempting to color elements of ℌ using expressions of elements of F as words in a certain generating set for F. From this, we derive information about not just the colorability of certain elements of ℌ, but also about all possible ways to color these elements. Because of this we raise (and answer some) questions about enumeration. We also bring in an extension E of the group F and ask whether certain elements "parametrize" the set of all colorings of the elements of ℌ that use all four colors.

Let R be a non-commutative ring. The commuting graph of R denoted by Γ(R), is a graph with vertex set R\Z(R) and two vertices a and b are adjacent if ab = ba. It has been shown that the diameter of Γ(R)^c is less than 3. For a finite ring R we show that the diameter of Γ(R)^c is one if and only if R is the non-commutative ring on 4 elements. Also we characterize all rings where the complements of their commuting graphs are planar. Moreover, we identify the commuting graphs of rings of order pⁱ for i = 2, 3 and prime number p.

Diophantine equations $5x^2+y_1^2+y_2^2=5x{y}_1{y}_2$ and $2x^2+y_1^2+y_2^2=4x{y}_1{y}_2$ are connected with the arithmetic once punctured torus groups having Fricke coordinates $(\sqrt{5},2\sqrt{5},5)$ and $(2\sqrt{2},2\sqrt{2},4)$. We describe and analyze the structure of these equations by a graph, which we call a two-color Markoff graph. The faces of the graph are labeled by matrices in the corresponding once punctured torus group, the word representation of which is easily described owing to arithmetic properties of the graph. As an application, we show that these matrices define Markoff minimal forms attaining the values of the Markoff spectrum given by the positive integer solutions of these equations.

The Markoff spectrum is defined as the set of normalized values of arithmetic minima of indefinite quadratic forms. In the theory of the Markoff spectrum we observe various kinds of symmetry. Each of Conway’s topographs of quadratic forms which give values in the discrete part of the Markoff spectrum has a special infinite path consisting of edges. It has symmetry with respect to a translation along the path and countable central symmetries by which the path is invariant. We prove that these properties are obtained from the fact that the path is a discretization of a geodesic in the upper half-plane which corresponds to a value of the discrete part of the Markoff spectrum and projects to a simple closed geodesic on the once punctured torus with the highest degree of symmetry.

A set D ⊆ V is a restrained dominating set of a graph G = (V, E) if every vertex in V\D is adjacent to a vertex in D and a vertex in V\D. Given a graph G and a positive integer k, the restrained domination problem is to check whether G has a restrained dominating set of size at most k. The restrained domination problem is known to be NP-complete even for chordal graphs. In this paper, we propose a linear time algorithm to compute a minimum restrained dominating set of a proper interval graph. We present a polynomial time reduction that proves the NP-completeness of the restrained domination problem for undirected path graphs, chordal bipartite graphs, circle graphs, and planar graphs.

A proper vertex coloring of $G$ is acyclic if $G$ contains no bicolored cycle. Namely, every cycle of $G$ must be colored with at least three colors. $G$ is acyclically $L$-colorable if for a given list assignment $L=\{L(v):v\in V\}$, there exists an acyclic coloring $\pi$ of $G$ such that $\pi (v)\in L(v)$ for all $v\in V$. If $G$ is acyclically $L$-colorable for any list assignment with $|L(v)|\ge k$ for all $v\in V$, then $G$ is acyclically $k$-choosable.

In this paper, we prove that planar graphs without intersecting $5^{-}$-cycles are acyclically $4$-choosable. This provides a sufficient condition for planar graphs to be acyclically 4-choosable and also strengthens a result in [M. Montassier, A. Raspaud and W. Wang, Acyclic 4-choosability of planar graphs without cycles of specific lengths, in Topics in Discrete Mathematics, Algorithms and Combinatorics, Vol. 26 (Springer, Berlin, 2006), pp. 473–491] which says that planar graphs without $4$-, $5$-cycles and intersecting 3-cycles are acyclically 4-choosable.

Let $G$ be a graph. An $(s,t)$-relaxed strong edge $k$-coloring is a mapping $\pi :E(G)\to \{1,2,\dots ,k\}$ such that for any edge $e$, there are at most $s$ edges adjacent to $e$ and $t$ edges which are distance two apart from $e$ assigned the same color as $e$. The $(s,t)$-relaxed strong chromatic index, denoted by ${\chi }_{(s,t)}^{\prime }(G)$, is the minimum number $k$ of an $(s,t)$-relaxed strong $k$-edge-coloring admitted by $G$. $G$ is called $(s,t)$-relaxed strong edge $L$-colorable if for a given list assignment $L=\{L(e)|e\in E(G)\}$, there exists an $(s,t)$-relaxed strong edge coloring $\pi$ of $G$ such that $\pi (e)\in L(e)$ for all $e\in E(G)$. If $G$ is $(s,t)$-relaxed strong edge $L$-colorable for any list assignment with $|L(e)|=k$ for all $e\in E(G)$, then $G$ is said to be $(s,t)$-relaxed strong edge $k$-choosable. The $(s,t)$-relaxed strong list chromatic index, denoted by ${\mathrm{\text{ch}}}_{(s,t)}^{\prime }(G)$, is defined to be the smallest integer $k$ such that $G$ is $(s,t)$-relaxed strong edge $k$-choosable.

In this paper, we prove that every planar graph $G$ with girth 6 satisfies that ${\mathrm{\text{ch}}}_{(1,0)}^{\prime }(G)\le 3\mathrm{\Delta }(G)-1$. This strengthens a result which says that every planar graph $G$ with girth 7 and $\mathrm{\Delta }(G)\ge 4$ satisfies that ${\chi }_{(1,0)}^{\prime }(G)\le 3\mathrm{\Delta }(G)-1$.

The $(2,1)$-total choice number of $G$, denoted by $C_{(2,1)}^T(G)$, is the minimum $k$ such that $G$ is $k$-$(2,1)$-total choosable. It was proved in [Y. Yu, X. Zhang and G. Z. Liu, List (d,1)-total labeling of graphs embedded in surfaces, Oper. Res. Trans.15(3) (2011) 29–37.] that $C_{p,1}^T(G)\le \mathrm{\Delta }+2p$ if $G$ is a graph embedded in surface with Euler characteristic $𝜀$ and $\mathrm{\Delta }(G)$ big enough. In this paper, we prove that: (i) if $G$ is a planar graph with $\mathrm{\Delta }(G)\ge 7$ and $3$-cycle is not adjacent to $k$-cycle, $k\in \{3,4\}$, then $C_{(2,1)}^T(G)\le \mathrm{\Delta }+4$; (ii) if $G$ is a planar graph with $\mathrm{\Delta }(G)\ge 8$ and $i$-cycle is not adjacent to $j$-cycle, where $i,j\in \{3,4,5\}$, then $C_{(2,1)}^T(G)\le \mathrm{\Delta }+3$.

This paper proves that for any integer $k\ge 1$, every planar graph $G$ of girth at least $8k-3$ has fractional DP-chromatic number at most $2+\frac{1}{k}$.

Let $H=(V,E)$ be a connected graph of size $n$. If $W$ is an ordered subset of distinct vertices in $H$ then the subset $W$ is said to be a resolving set for $H$, if all of the vertices in the graph can be uniquely defined by the vector of distances to the vertices in $W$. A resolving set $W$ with minimum possible vertices is said to be a metric basis for $H$. The cardinality of the metric basis is called the metric dimension of the graph $H$. In this paper, we demonstrate that the metric dimension for some families of related planar graphs is three.

Given a graph $G=(V(G),E(G))$ and a proper total $k$-coloring $\mu$: $V(G)\cup E(G)\to \{1,2,\dots ,k\}$, we call $\mu$ neighbor sum distinguishing total coloring provided $h(v)\ne h(u)$ for any $uv\in E(G)$ where $h(v)=\mu (v)+{\sum }_{uv\in E(G)}\mu (uv)$ for any $v\in V(G)$. Neighbor sum distinguishing total coloring was first defined by Pilśniak and Woźniak. They conjectured $\mathrm{\Delta }(G)+3$ colors enable any graph $G$ to admit such a coloring. The neighbor sum distinguishing total chromatic number ${\chi }_{\mathrm{\Sigma }}^{\prime \prime }$ is the minimum integer where a graph is needed for this coloring. In this paper, we present two conclusions that ${\chi }_{\mathrm{\Sigma }}^{\prime \prime }\le \mathrm{\Delta }(G)+2$ provided there are no 3-cycles adjacent to 4-cycles in a planar graph $G$ with $\mathrm{\Delta }(G)\ge 8$ without cut edges, and ${\chi }_{\mathrm{\Sigma }}^{\prime \prime }\le \mathrm{\Delta }(G)+3$ provided there are no 4-cycles intersecting with 6-cycles in a planar graph $G$ with $\mathrm{\Delta }(G)\ge 7$.