We provide theoretical insights around the cutwidth of a graph and One-Sided Crossing Minimization (OSCM) problem. OSCM was posed in Parameterized Algorithms Computational Experiments Challenge 2024, where input parameter parameterized track. prove an asymptotically sharp upper bound on size terms its order cutwidth. As number so-called unsuited pairs is one factors that determine difficulty instance, we them $n$ graph. If bounded by constant, this implies $\mathcal{O}(2^n)$-time algorithm,...

The band-, tree-, and clique-width are of primary importance in algorithmic graph theory due to the fact that many problems NP-hard for general graphs can be solved polynomial time when restricted where one these parameters is bounded. It known any fixed $\Delta \geq 3$, all three unbounded with vertex degree at most $Delta$. In this paper, we distinguish representative subclasses bounded have or clique-width. Our proofs constructive lead efficient algorithms a variety those classes.

Let $G$ be a finite, simple, and undirected graph let $S$ set of vertices $G$. If no vertex that does not belong to has two neighbors in $S$, then is $P_3$-convex. The $P_3$-convex hull $H_G(S)$ the smallest containing $S$. $P_3$-Carathéodory number integer $c$ such for every $u$ $H_G(S)$, there $F\subseteq S$ with $|F|\leq c$ $u\in H_G(F)$. We study structural algorithmic aspects number. characterize trees block graphs, establish upper bounds on general graphs claw-free prove it NP-complete...

A set of vertices C in a graph is convex if it contains all which lie on shortest paths between C. The hull S the smallest containing S. number $h(G)$ G cardinality whose vertex G. For connected triangle-free order n and diameter d at least 4, we prove that $h(G)\leq(n-d+3)/3$ has minimum degree 3 $h(G)\leq2(n-d+5)/7$, cubic. Furthermore for n, girth g 5, 2, d, $h(G)\leq2+(n-d-1)/\left\lceil\frac{g-1}{2}\right\rceil$. All bounds are best possible.

We prove that a cubic graph with $m$ edges has an induced matching at least $m/9$ edges. Our result generalizes for planar graphs due to Kang, Mnich, and Müller (SIAM J. Discrete Math., 26 (2012), pp. 1383--1411) solves conjecture of Henning Rautenbach.

The MIX technique forms the basis of many popular services that offer anonymity communication in open and shared networks such as Internet. In this paper, fundamental limits on provided by are found considering two different settings. First, we consider an information theoretic setting to determine extent inherent observations traffic passing through MIX. We show if size sender sets is less than total user population, contained sufficient deduce all relationships between senders receivers...

Abstract As our main result, we prove that for every multigraph G = ( V, E ) which has no loops and is of order n , size m maximum degree $\Delta < {{{10}}^{-{{3}}}{{m}}\over \sqrt{{{8}}{{n}}}}$ there a mapping ${{f}}:{{V}}\cup {{E}}\to \big\{{{1}},{{2}},\ldots,\big\lceil{{{m}}+{{2}}\over {{3}}}\big\rceil\big\}$ such ${{f}}({{u}})+{{f}}({{uv}})+{{f}}({{v}})\not={{f}}({{u}}')+{{f}}({{u}}'{{v}}')+{{f}}({{v}}')$ ${{uv}},{{u}}'{{v}}'\in {{E}}$ with ${{uv}}\not={{u}}'{{v}}'$ . Functions this...

Let $G$ be a graph of order $n$. $\mathrm{lpt}(G)$ the minimum cardinality set $X$ vertices such that intersects every longest path $G$, and define $\mathrm{lct}(G)$ analogously for cycles instead paths. We prove $\mathrm{lpt}(G)\leqslant \lceil\frac{n}{4}-\frac{n^{2/3}}{90}\rceil$ if is connected, $\mathrm{lct}(G)\leqslant \lceil\frac{n}{3}-\frac{n^{2/3}}{36}\rceil$ $2$-connected. Our bound on improves an earlier result Thomassen. Furthermore, we upper bounds planar graphs bounded tree-width.