Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the deficiency of complete multipartite graphs
129
0
0.0
(
0
)
Added by
Petros Petrosyan
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$.
A emph{proper $t$-edge-coloring} of a graph $G$ is a mapping $alpha: E(G)rightarrow {1,ldots,t}$ such that all colors are used, and $alpha(e) eq alpha(e^{prime})$ for every pair of adjacent edges $e,e^{prime}in E(G)$. If $alpha $ is a proper edge-coloring of a graph $G$ and $vin V(G)$, then emph{the spectrum of a vertex $v$}, denoted by $Sleft(v,alpha right)$, is the set of all colors appearing on edges incident to $v$. emph{The deficiency of $alpha$ at vertex $vin V(G)$}, denoted by $def(v,alpha)$, is the minimum number of integers which must be added to $Sleft(v,alpha right)$ to form an interval, and emph{the deficiency $defleft(G,alpharight)$ of a proper edge-coloring $alpha$ of $G$} is defined as the sum $sum_{vin V(G)}def(v,alpha)$. emph{The deficiency of a graph $G$}, denoted by $def(G)$, is defined as follows: $def(G)=min_{alpha}defleft(G,alpharight)$, where minimum is taken over all possible proper edge-colorings of $G$. For a graph $G$, the smallest and the largest values of $t$ for which it has a proper $t$-edge-coloring $alpha$ with deficiency $def(G,alpha)=def(G)$ are denoted by $w_{def}(G)$ and $W_{def}(G)$, respectively. In this paper, we obtain some bounds on $w_{def}(G)$ and $W_{def}(G)$. In particular, we show that for any $lin mathbb{N}$, there exists a graph $G$ such that $def(G)>0$ and $W_{def}(G)-w_{def}(G)geq l$. It is known that for the complete graph $K_{2n+1}$, $def(K_{2n+1})=n$ ($nin mathbb{N}$). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Ha{l}uszczak posed the following conjecture on the deficiency of near-complete graphs: if $nin mathbb{N}$, then $def(K_{2n+1}-e)=n-1$. In this paper, we confirm this conjecture.
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 colors $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}$.
Motivated by analogous questions in the setting of Steiner triple systems and Latin squares, Nenadov, Sudakov and Wagner [Completion and deficiency problems, Journal of Combinatorial Theory Series B, 2020] recently introduced the notion of graph deficiency. Given a global spanning property $mathcal P$ and a graph $G$, the deficiency $text{def}(G)$ of the graph $G$ with respect to the property $mathcal P$ is the smallest non-negative integer $t$ such that the join $G*K_t$ has property $mathcal P$. In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an $n$-vertex graph $G$ needs to ensure $G*K_t$ contains a $K_r$-factor (for any fixed $rgeq 3$). In this paper we resolve their problem fully. We also give an analogous result which forces $G*K_t$ to contain any fixed bipartite $(n+t)$-vertex graph of bounded degree and small bandwidth.
A proper edge coloring of a graph $G$ with colors $1,2,dots,t$ is called a cyclic interval $t$-coloring if for each vertex $v$ of $G$ the edges incident to $v$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. In this paper we introduce and investigate a new notion, the cyclic deficiency of a graph $G$, defined as the minimum number of pendant edges whose attachment to $G$ yields a graph admitting a cyclic interval coloring; this number can be considered as a measure of closeness of $G$ of being cyclically interval colorable. We determine or bound the cyclic deficiency of several families of graphs. In particular, we present examples of graphs of bounded maximum degree with arbitrarily large cyclic deficiency, and graphs whose cyclic deficiency approaches the number of vertices. Finally, we conjecture that the cyclic deficiency of any graph does not exceed the number of vertices, and we present several results supporting this conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
