TITLE

$$l_p$$ -Optimal Rankings and Max-Optimal Rankings are Different

AUTHOR(S)
Jacob, Bonnie; Jacob, Jobby
PUB. DATE
November 2017
SOURCE
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1473
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
A k-ranking of a graph G is a function $$f: V(G) \rightarrow \left\{ 0, 1, \ldots , k-1 \right\}$$ such that if $$f(u)=f(v)$$ for any $$u, v \in V(G)$$ , then on every uv path in G, there exists a vertex w with $$f(w) > f(u)$$ . The optimality of a k-ranking is measured in terms of the $$l_{\infty }$$ norm of the sequence of labels produced by the k-ranking (max optimality). We study the optimality of rankings of graphs under all $$l_p$$ norms. In particular, we show that there exist graphs where no max-optimal rankings are $$l_p$$ optimal for any non-negative finite real number p, and vice versa.
ACCESSION #
126308057

Related Articles

• Translating Integer Factoring into Graph Coloring. JENSEN, TOMMY RENÉ // Kyungpook Mathematical Journal;Jun2016, Vol. 56 Issue 2, p611

This paper gives for every positive integer n an explicit construction of a graph G with fewer than 15 logÂ²n -- 5/2 log n. +28 vertices, such that there exists a nontrivial factoring of n if and only if G is 3-colorable.

• On graphs double-critical with respect to the colouring number. Kriesell, Matthias; Pedersen, Anders Sune // Discrete Mathematics & Theoretical Computer Science (DMTCS);2015, Vol. 17 Issue 2, p49

The colouring number col(G) of a graph G is the smallest integer Îº for which there is an ordering of the vertices of G such that when removing the vertices of G in the specified order no vertex of degree more than Îº -- 1 in the remaining graph is removed at any step. An edge e of a graph G...

• Solution to Some Open Problems on E-super Vertex Magic Total Labeling of Graphs. Marimuthu, G.; Raja Durga, M. S.; Devi, G. Durga // Applications & Applied Mathematics;Dec2015, Vol. 10 Issue 2, p1104

Let G be a finite graph with p vertices and q edges. A vertex magic total labeling is a bijection f from V(G)âˆªE(G) to the consecutive integers 1, 2, ..., p+q with the property that for every uâˆŠV(G), f(u)+ Î£vâˆŠN(u)f(uv) =k for some constant k. Such a labeling is E-super if f...

• The convex recoloring problem: polyhedra, facets and computational experiments. Campêlo, Manoel; Freire, Alexandre; Lima, Karla; Moura, Phablo; Wakabayashi, Yoshiko // Mathematical Programming;Mar2016, Vol. 156 Issue 1/2, p303

A coloring of the vertices of a graph $$G$$ is convex if the vertices receiving a common color induce a connected subgraph of $$G$$ . We address the convex recoloring problem: given a graph $$G$$ and a coloring of its vertices, recolor a minimum number of vertices of $$G$$ , so that the...

• The Scrambling Index of a Class of Two-colored Hamiltonian Digraphs. Mardiningsih; Pasaribu, Merryanty L. // AIP Conference Proceedings;2016, Vol. 1775 Issue 1, p1

The scrambling index of a two-colored digraph is the least positive integer h + â„“ over all pairs of nonnegative integers (h, â„“) such that for each pair of vertices u and v there is a vertex w with the property that there exist a walk from u to w and a walk from v to w that consist...

• A NEIGHBORHOOD UNION CONDITION FOR FRACTIONAL (k; n';m)-CRITICAL DELETED GRAPHS. YUN GAO; FARAHANI, MOHAMMAD REZA; WEI GAO // Transactions on Combinatorics;2017, Vol. 6 Issue 1, p13

A graph G is called a fractional (k; n ' ;m)-critical deleted graph if any n ' vertices are removed from G the resulting graph is a fractional (k;m)-deleted graph. In this paper, we prove that for integers for each pair of non-adjacent vertices x, y of G, then G is a fractional (k; n '...

• THE CONDITION FOR A SEQUENCE TO BE POTENTIALLY AL,M- GRAPHIC. PIRZADA, SHARIEFUDDIN; CHAT, BILAL A. // Transactions on Combinatorics;2017, Vol. 6 Issue 1, p21

The set of all non-increasing non-negative integer sequences Ï€ = (d1, d2,...,dn) is denoted by NSn. A sequence Ï€ Îµ NSn is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of Ï€. The set of all graphic...

• Signed Roman $$k$$ -Domination in Graphs. Henning, Michael; Volkmann, Lutz // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p175

Let $$k\ge 1$$ be an integer, and let $$G$$ be a finite and simple graph with vertex set $$V(G)$$ . A signed Roman $$k$$ -dominating function (SRkDF) on a graph $$G$$ is a function $$f:V(G)\rightarrow \{-1,1,2\}$$ satisfying the conditions that (i) $$\sum _{x\in N[v]}f(x)\ge k$$ for each vertex...

• One Modulo N Gracefullness Of Arbitrary Supersubdivisions of Graphs. Ramachandran, V.; Sekar, C. // International Journal of Mathematical Combinatorics;Jun2014, Vol. 2, p36

A function f is called a graceful labelling of a graph G with q edges if f is an injection from the vertices of G to the set {0,1, 2,..., q} such that, when each edge xy is assigned the label |f(x) -- f(y)|, the resulting edge labels are distinct. A graph G is said to be one modulo N graceful...

• Cycle Lengths of Hamiltonian $$P_\ell$$ -free Graphs. Meierling, Dirk; Rautenbach, Dieter // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2335

For an integer $$\ell$$ at least three, we prove that every Hamiltonian $$P_\ell$$ -free graph $$G$$ on $$n>\ell$$ vertices has cycles of at least $$\frac{2}{\ell }n-1$$ different lengths. For small values of $$\ell$$ , we can improve the bound as follows. If $$4\le \ell \le 7$$ , then $$G$$...

Share