ﻻ يوجد ملخص باللغة العربية
For a real constant $alpha$, let $pi_3^alpha(G)$ be the minimum of twice the number of $K_2$s plus $alpha$ times the number of $K_3$s over all edge decompositions of $G$ into copies of $K_2$ and $K_3$, where $K_r$ denotes the complete graph on $r$ vertices. Let $pi_3^alpha(n)$ be the maximum of $pi_3^alpha(G)$ over all graphs $G$ with $n$ vertices. The extremal function $pi_3^3(n)$ was first studied by GyH{o}ri and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320]. In a recent progress on this problem, Kral, Lidicky, Martins and Pehova [Decomposing graphs into edges and triangles, Combin. Prob. Comput. 28 (2019) 465--472] proved via flag algebras that $pi_3^3(n)le (1/2+o(1))n^2$. We extend their result by determining the exact value of $pi_3^alpha(n)$ and the set of extremal graphs for all $alpha$ and sufficiently large $n$. In particular, we show for $alpha=3$ that $K_n$ and the complete bipartite graph $K_{lfloor n/2rfloor,lceil n/2rceil}$ are the only possible extremal examples for large $n$.
A graph is locally irregular if any pair of adjacent vertices have distinct degrees. A locally irregular decomposition of a graph $G$ is a decomposition $mathcal{D}$ of $G$ such that every subgraph $H in mathcal{D}$ is locally irregular. A graph is s
We prove that for $k in mathbb{N}$ and $d leq 2k+2$, if a graph has maximum average degree at most $2k + frac{2d}{d+k+1}$, then $G$ decomposes into $k+1$ pseudoforests, where one of the pseudoforests has all connected components having at most $d$ edges.
Given a graph $G$, a decomposition of $G$ is a partition of its edges. A graph is $(d, h)$-decomposable if its edge set can be partitioned into a $d$-degenerate graph and a graph with maximum degree at most $h$. For $d le 4$, we are interested in the
A graph $G$ is called interval colorable if it has a proper edge coloring with colors $1,2,3,dots$ such that the colors of the edges incident to every vertex of $G$ form an interval of integers. Not all graphs are interval colorable; in fact, quite f
In 2006, Barat and Thomassen posed the following conjecture: for each tree $T$, there exists a natural number $k_T$ such that, if $G$ is a $k_T$-edge-connected graph and $|E(G)|$ is divisible by $|E(T)|$, then $G$ admits a decomposition into copies o