Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn deficiency problems for graphs
135
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 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 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.
The general position number of a graph $G$ is the size of the largest set of vertices $S$ such that no geodesic of $G$ contains more than two elements of $S$. The monophonic position number of a graph is defined similarly, but with `induced path in place of `geodesic. In this paper we investigate some extremal problems for these parameters. Firstly we discuss the problem of the smallest possible order of a graph with given general and monophonic position numbers, with applications to a realisation result. We then solve a Tur{a}n problem for the size of graphs with given order and position numbers and characterise the possible diameters of graphs with given order and monophonic position number. Finally we classify the graphs with given order and diameter and largest possible general position number.
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph $(G,sigma)$, equipped with lists $L(v) subseteq V(H), v in V(G)$, of allowed images, to a fixed target signed graph $(H,pi)$. The complexity of the similar homomorphism problem without lists (corresponding to all lists being $L(v)=V(H)$) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. We illustrate this difficulty by classifying the complexity of the problem when $H$ is a tree (with possible loops). The tools we develop will be useful for classifications of other classes of signed graphs, and we illustrate this by classifying the complexity of irreflexive signed graphs in which the unicoloured edges form some simple structures, namely paths or cycles. The structure of the signed graphs in the polynomial cases is interesting, suggesting they may constitute a nice class of signed graphs analogous to the so-called bi-arc graphs (which characterized the polynomial cases of list homomorphisms to unsigned graphs).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
