On the semi-proper orientations of graphs

DOI10.1016/J.DAM.2020.07.003MaRDI QIDQ2663989zbMATH OpenOpenAlexFDO

Authors A. Dehghan, Frédéric Havet

Publication date 20 April 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.02867

zbMATH Keywords

planar graphsproper orientation numbersemi-proper orientationweighted orientation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A {it semi-proper orientation} of a given graph $G$ is a function $(D,w)$ that assigns an orientation $D(e)$ and a positive integer weight $w(e)$ to each edge $e$ such that for every two adjacent vertices $v$ and $u$, $S_{(D,w)}(v)eq{S}_{(D,w)}(u)$, where $S_{(D,w)}(v)$ is the sum of the weights of edges with head $v$ in $D$. The {it semi-proper orientation number} of a graph $G$, denoted by $overrightarrow{chi}_s(G)$, is $mi{n}_{(D,w)inGamma}ma{x}_{vinV(G)}{S}_{(D,w)}(v)$, where $Gamma$ is the set of all semi-proper orientations of $G$. The {it optimal semi-proper orientation} is a semi-proper orientation $(D,w)$ such that $ma{x}_{vinV(G)}{S}_{(D,w)}(v)=overrightarrow{chi}_s(G)$. In this work, we show that every graph $G$ has an optimal semi-proper orientation $(D,w)$ such that the weight of each edge is one or two. Next, we show that determining whether a given planar graph $G$ with $overrightarrow{chi}_s(G)=2$ has an optimal semi-proper orientation $(D,w)$ such that the weight of each edge is one is NP-complete. Finally, we prove that the problem of determining the semi-proper orientation number of planar bipartite graphs is NP-hard.

Recommendations

• Note on (semi-)proper orientation of some triangulated planar graphs
• Proper orientation, proper biorientation and semi-proper orientation numbers of graphs
• Proper orientations of planar bipartite graphs
• Proper orientations and proper chromatic number
• Weighted proper orientations of trees and graphs of bounded treewidth

Cites work

• Coloring chip configurations on graphs and digraphs
• Computation of lucky number of planar graphs is NP-hard
• Edge weights and vertex colours
• Hard tiling problems with simple tiles
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Is there any polynomial upper bound for the universal labeling of graphs?
• On the proper orientation number of bipartite graphs
• Proper orientation of cacti
• Proper orientations of planar bipartite graphs
• Sequence variations of the 1-2-3 conjecture and irregularity strength
• The 1,2,3-conjecture and 1,2-conjecture for sparse graphs
• The complexity of the proper orientation number
• Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs
• Weighted proper orientations of trees and graphs of bounded treewidth

Cited in

(12)

• A generalization of Sperner's theorem and an application to graph orientations
• On the in-out-proper orientations of graphs
• On the proper arc labeling of directed graphs
• Weighted proper orientations of trees and graphs of bounded treewidth
• Note on (semi-)proper orientation of some triangulated planar graphs
• Proper orientation, proper biorientation and semi-proper orientation numbers of graphs
• Proper orientation of cacti
• Completing orientations of partially oriented graphs
• On the Structure of the Strong Orientations of a Graph
• A note on orientations of mixed graphs
• Semi-proper orientations of dense graphs
• On preserving full orientability of graphs

This page was built for publication: On the semi-proper orientations of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2663989)