اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAddressing Johnson graphs, complete multipartite graphs, odd cycles and other graphs
84
0
0.0
(
0
)
نشر من قبل
Sebastian M. Cioab\\u{a}
تاريخ النشر
2018
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Graham and Pollak showed that the vertices of any graph $G$ can be addressed with $N$-tuples of three symbols, such that the distance between any two vertices may be easily determined from their addresses. An addressing is optimal if its length $N$ is minimum possible. In this paper, we determine an addressing of length $k(n-k)$ for the Johnson graphs $J(n,k)$ and we show that our addressing is optimal when $k=1$ or when $k=2, n=4,5,6$, but not when $n=6$ and $k=3$. We study the addressing problem as well as a variation of it in which the alphabet used has more than three symbols, for other graphs such as complete multipartite graphs and odd cycles. We also present computations describing the distribution of the minimum length of addressings for connected graphs with up to $10$ vertices. Motivated by these computations we settle a problem of Graham, showing that most graphs on $n$ vertices have an addressing of length at most $n-(2-o(1))log_2 n$.
قيم البحث
اقرأ أيضاً
An edge-coloring of a graph $G$ with colors $1,ldots,t$ is an emph{interval $t$-coloring} if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an integer interval. It is well-known that there are graphs
that do not have interval colorings. The emph{deficiency} of a graph $G$, denoted by $mathrm{def}(G)$, is the minimum number of pendant edges whose attachment to $G$ leads to a graph admitting an interval coloring. In this paper we investigate the problem of determining or bounding of the deficiency of complete multipartite graphs. In particular, we obtain a tight upper bound for the deficiency of complete multipartite graphs. We also determine or bound the deficiency for some classes of complete multipartite graphs.
A total coloring of a graph $G$ is a coloring of its vertices and edges such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. An interval total $t$-coloring of a graph $G$ is a total coloring of $G$ with col
ors $1,ldots,t$ such that all colors are used, and the edges incident to each vertex $v$ together with $v$ are colored by $d_{G}(v)+1$ consecutive colors, where $d_{G}(v)$ is the degree of a vertex $v$ in $G$. In this paper we prove that all complete multipartite graphs with the same number of vertices in each part are interval total colorable. Moreover, we also give some bounds for the minimum and the maximum span in interval total colorings of these graphs. Next, we investigate interval total colorings of hypercubes $Q_{n}$. In particular, we prove that $Q_{n}$ ($ngeq 3$) has an interval total $t$-coloring if and only if $n+1leq tleq frac{(n+1)(n+2)}{2}$.
We prove that if $G$ is a $k$-partite graph on $n$ vertices in which all of the parts have order at most $n/r$ and every vertex is adjacent to at least a $1-1/r+o(1)$ proportion of the vertices in every other part, then $G$ contains the $(r-1)$-st power of a Hamiltonian cycle
In this paper, we investigate the ratio of the numbers of odd and even cycles in outerplanar graphs. We verify that the ratio generally diverges to infinity as the order of a graph diverges to infinity. We also give sharp estimations of the ratio for
several classes of outerplanar graphs, and obtain a constant upper bound of the ratio for some of them. Furthermore, we consider similar problems in graphs with some pairs of forbidden subgraphs/minors, and propose a challenging problem concerning claw-free graphs.
Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $(G,c)$ contains a rainbow cycle of length at most $lceil frac{n}{2} rceil$, which is best possible.
Our result settles a special case of a strengthening of the Caccetta-Haggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
