Fractional and circular separation dimension of graphs

DOI10.1016/J.EJC.2017.09.001MaRDI QIDQ1686246zbMATH OpenOpenAlexFDO

Authors Sarah Loeb, Douglas B. West

Publication date 21 December 2017

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

circular orderingslinear orderings

Mathematics Subject Classification ID

Distance in graphs (05C12)

Abstract: The separation dimension of a graph $G$, written $pi(G)$, is the minimum number of linear orderings of $V(G)$ such that every two nonincident edges are "separated" in some ordering, meaning that both endpoints of one edge appear before both endpoints of the other. We introduce the fractional separation dimension $p{i}_f(G)$, which is the minimum of $a/b$ such that some $a$ linear orderings (repetition allowed) separate every two nonincident edges at least $b$ times. In contrast to separation dimension, fractional separation dimension is bounded: always $p{i}_f(G)le3$, with equality if and only if $G$ contains $K_4$. There is no stronger bound even for bipartite graphs, since $p{i}_f(K_{m,m})=p{i}_f(K_{m+1,m})=frac3mm+1$. We also compute $p{i}_f(G)$ for cycles and some complete tripartite graphs. We show that $p{i}_f(G)<sqrt2$ when $G$ is a tree and present a sequence of trees on which the value tends to $4/3$. Finally, we consider analogous problems for circular orderings, where pairs of nonincident edges are separated unless their endpoints alternate. Let $p{i}^{c}irc(G)$ be the number of circular orderings needed to separate all pairs and $p{i}_f^{c}irc(G)$ be the fractional version. Among our results: (1) $p{i}^{c}irc(G)=1$ if and only $G$ is outerplanar. (2) $p{i}^{c}irc(G)le2$ when $G$ is bipartite. (3) $p{i}^{c}irc(K_n)gelo{g}_{2}lo{g}_3(n-1)$. (4) $p{i}_f^{c}irc(G)lefrac32$, with equality if and only if $K_{4}subseteqG$. (5) $p{i}_f^{c}irc(K_{m,m})=frac3m-32m-1$.

Recommendations

• Circular separation dimension of a subclass of planar graphs
• Separation dimension of bounded degree graphs
• Separation dimension and degree
• Separation dimension of graphs and hypergraphs
• Separation dimension and sparsity

Cites work

• Boxicity and separation dimension
• Explicit construction of linear sized tolerant networks
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• Induced separation dimension
• Ramanujan graphs
• Separation dimension of bounded degree graphs
• Separation dimension of graphs and hypergraphs

Cited in

(10)

• Separation dimension of graphs and hypergraphs
• Induced separation dimension
• Separation dimension of bounded degree graphs
• The fractional metric dimension of graphs
• Separation dimension and sparsity
• Circular separation dimension of a subclass of planar graphs
• Separation dimension and degree
• Perfect and nearly perfect separation dimension of complete and random graphs
• A survey on the boxicity and cubicity of graphs
• The induced separation dimension of a graph

This page was built for publication: Fractional and circular separation dimension of graphs

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