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
Academic Journal
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

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics