On coupon colorings of graphs Chen, Bob; Kim, Jeong Han; Tait, Michael ...
Discrete Applied Mathematics,
10/2015, Volume:
193
Journal Article
Peer reviewed
Open access
Let G be a graph with no isolated vertices. A k-coupon coloring of G is an assignment of colors from k≔{1,2,…,k} to the vertices of G such that the neighborhood of every vertex of G contains vertices ...of all colors from k. The maximum k for which a k-coupon coloring exists is called the coupon coloring number of G, and is denoted χc(G). In this paper, we prove that every d-regular graph G has χc(G)≥(1−o(1))d/logd as d→∞, and the proportion of d-regular graphs G for which χc(G)≤(1+o(1))d/logd tends to 1 as |V(G)|→∞.
An injectivek-coloring of a graph G is an assignment of colors from k to the vertices of G such that no two vertices joined by a path of length two in G have the same color. The minimum k for which such a coloring exists is called the injective coloring number of G, denoted χi(G). In this paper, we also discuss injective colorings of Hamming graphs.
We prove the non-existence of extended perfect codes in H(n,q), where q=3,4 and n>q+2 or both n and q are odd. In particular, we prove the non-existence of non-linear (q+2,qq−1,4)q MDS codes when q ...is odd.
A set of vertices $S$ resolves a graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The metric dimension of $G$ is the minimum cardinality of a ...resolving set of $G$. This paper studies the metric dimension of cartesian products $G\,\square\,H$. We prove that the metric dimension of $G\,\square\,G$ is tied in a strong sense to the minimum order of a so-called doubly resolving set in $G$. Using bounds on the order of doubly resolving sets, we establish bounds on $G\,\square\,H$ for many examples of $G$ and $H$. One of our main results is a family of graphs $G$ with bounded metric dimension for which the metric dimension of $G\,\square\,G$ is unbounded.
A <inline-formula> <tex-math notation="LaTeX">\lambda </tex-math></inline-formula>-fold <inline-formula> <tex-math notation="LaTeX">{r} </tex-math></inline-formula>-packing (multiple ...radius-<inline-formula> <tex-math notation="LaTeX">{r} </tex-math></inline-formula> covering) in a Hamming metric space is a code <inline-formula> <tex-math notation="LaTeX">{C} </tex-math></inline-formula> such that the radius-<inline-formula> <tex-math notation="LaTeX">{r} </tex-math></inline-formula> balls centered in the codewords of <inline-formula> <tex-math notation="LaTeX">{C} </tex-math></inline-formula> cover each vertex of the space by not more (not less, respectively) than <inline-formula> <tex-math notation="LaTeX">\lambda </tex-math></inline-formula> times. The well-known <inline-formula> <tex-math notation="LaTeX">{r} </tex-math></inline-formula>-error-correcting codes correspond to the case <inline-formula> <tex-math notation="LaTeX">\lambda =1 </tex-math></inline-formula>, while in general multifold <inline-formula> <tex-math notation="LaTeX">{r} </tex-math></inline-formula>-packing are related with list decodable codes. We (a) propose asymptotic bounds for the maximum size of a <inline-formula> <tex-math notation="LaTeX">{q} </tex-math></inline-formula>-ary 2-fold 1-packing as <inline-formula> <tex-math notation="LaTeX">{q} </tex-math></inline-formula> grows; (b) prove that a <inline-formula> <tex-math notation="LaTeX">{q} </tex-math></inline-formula>-ary distance-2 MDS code of length <inline-formula> <tex-math notation="LaTeX">{n} </tex-math></inline-formula> is an optimal <inline-formula> <tex-math notation="LaTeX">{n} </tex-math></inline-formula>-fold 1-packing if <inline-formula> <tex-math notation="LaTeX">{q}\ge 2{n} </tex-math></inline-formula>; (c) derive an upper bound for the size of a binary <inline-formula> <tex-math notation="LaTeX">\lambda </tex-math></inline-formula>-fold 1-packing and a lower bound for the size of a binary multiple radius-1 covering (the last bound allows to update the small-parameters table); (d) classify all optimal binary 2-fold 1-packings up to length 9, in particular, establish the maximum size 96 of a binary 2-fold 1-packing of length 9; (e) prove some properties of 1-perfect unitrades, which are a special case of 2-fold 1-packings.
AbstractInterval function of a graph is a well-known notion in metric graph theory and the axiomatic characterization using a set of first order axioms of different graph classes is an interesting ...problem in this area. Partial cubes and partial Hamming graphs form one of the central graph class that can be embedded into hypercubes and Hamming graphs respectively. In this paper we present an axiomatic characterization of the interval function of partial cubes and partial Hamming graphs, using different first order axioms. Further, we give an axiomatic characterization of the interval function of these graphs using axioms on an arbitrary function R on V.
The reconstruction of an object of a given class by its intersection with some (so-called testing) set is studied. For the class, we consider Preparata-like codes, i.e., nonlinear codes of length
,
, ...with code distance 5 and twice the size of a linear code of the same length and distance. Conditions are determined under which the union of a few concentric spheres forms a testing set for Preparata-like codes.
Numerous data analysis and data mining techniques require that data be embedded in a Euclidean space. When faced with symbolic datasets, particularly biological sequence data produced by ...high-throughput sequencing assays, conventional embedding approaches like binary and
k
-mer count vectors may be too high dimensional or coarse-grained to learn from the data effectively. Other representation techniques such as Multidimensional Scaling (MDS) and Node2Vec may be inadequate for large datasets as they require recomputing the full embedding from scratch when faced with new, unclassified data. To overcome these issues we amend the graph-theoretic notion of “metric dimension” to that of “multilateration.” Much like trilateration can be used to represent points in the Euclidean plane by their distances to three non-colinear points, multilateration allows us to represent any node in a graph by its distances to a subset of nodes. Unfortunately, the problem of determining a minimal subset and hence the lowest dimensional embedding is NP-complete for general graphs. However, by specializing to Hamming graphs, which are particularly well suited to representing biological sequences, we can readily generate low-dimensional embeddings to map sequences of arbitrary length to a real space. As proof-of-concept, we use MDS, Node2Vec, and multilateration-based embeddings to classify DNA 20-mers centered at intron–exon boundaries. Although these different techniques perform comparably, MDS and Node2Vec potentially suffer from scalability issues with increasing sequence length whereas multilateration provides an efficient means of mapping long genomic sequences.
PDF
