Scholarlink

<p>Locally irregular graphs are those graphs in which any two adjacent vertices have different degrees, while locally irregular decompositions are edge-partitions of graphs where each part induces a locally irregular graph. These notions were introduced in a seminal work of Baudon et al., in connection, in particular, to the so-called 1-2-3 Conjecture. Since then, several of their aspects of interest have been investigated in the literature, including the existence of such decompositions with few parts, and the complexity of finding such ones. In this work, we pursue investigations on generalisations of these notions to digraphs. In particular, we mainly investigate one variant in which the notion of irregularity for a digraph requires, for every arc from a vertex <i>u</i> to a vertex <i>v</i>, the outdegree of <i>u</i> be different from the indegree of <i>v</i>. We establish several results on this variant, covering upper bounds on the number of needed parts in decompositions, complexity aspects, and the impact of being able to choose the graph orientation, which results we compare to both the undirected setting and previous investigations on the directed one.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Irregularity Notions for Digraphs

  • 期刊论文

  • 发表日期：

    2025年4月18日

查看全文
  • Julien Bensmail,
  • Thomas Filasto,
  • Hervé Hocquard,
  • Clara Marcille

摘要

Locally irregular graphs are those graphs in which any two adjacent vertices have different degrees, while locally irregular decompositions are edge-partitions of graphs where each part induces a locally irregular graph. These notions were introduced in a seminal work of Baudon et al., in connection, in particular, to the so-called 1-2-3 Conjecture. Since then, several of their aspects of interest have been investigated in the literature, including the existence of such decompositions with few parts, and the complexity of finding such ones. In this work, we pursue investigations on generalisations of these notions to digraphs. In particular, we mainly investigate one variant in which the notion of irregularity for a digraph requires, for every arc from a vertex u to a vertex v, the outdegree of u be different from the indegree of v. We establish several results on this variant, covering upper bounds on the number of needed parts in decompositions, complexity aspects, and the impact of being able to choose the graph orientation, which results we compare to both the undirected setting and previous investigations on the directed one.