Arbitrarily Edge-Partitionable Graphs - INRIA - Institut National de Recherche en Informatique et en Automatique
Article Dans Une Revue Discrete Applied Mathematics Année : 2025

Arbitrarily Edge-Partitionable Graphs

Résumé

In this work, we introduce and study the notion of arbitrarily edge-partitionable (AEP) graphs, as an edge version of arbitrarily partitionable (AP) graphs. A graph $G$ with order $n$ is AP if, for every partition $(\lambda_1,\dots,\lambda_p)$ of $n$, there is a partition $(V_1,\dots,V_p)$ of $V(G)$ where $G[V_i]$ is a connected graph with order $\lambda_i$, for every $i \in \{1,\dots,p\}$. Likewise, a graph $G$ with size $m$ is AEP if, for every partition $(\lambda_1,\dots,\lambda_p)$ of $m$, there is a partition $(E_1,\dots,E_p)$ of $E(G)$ where $G[E_i]$ is a connected graph with size $\lambda_i$, for every $i \in \{1,\dots,p\}$. We here mostly investigate how the most influential results on AP graphs adapt (or not) to AEP graphs. In particular, aspects we cover include connectivity properties, connections with Hamiltonian and traceable graphs, minimality notions, and (positive and negative) algorithmic results. One additional motivation behind our results, is that a graph is AEP if and only if its line graph is AP; therefore, our investigations can also be perceived as a way to study the AP property in the context of particular classes of line graphs.
Fichier principal
Vignette du fichier
aep.pdf (520.22 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04405426 , version 1 (19-01-2024)
hal-04405426 , version 2 (29-09-2024)

Identifiants

Citer

Julien Bensmail. Arbitrarily Edge-Partitionable Graphs. Discrete Applied Mathematics, 2025, 360, pp.428-442. ⟨10.1016/j.dam.2024.09.033⟩. ⟨hal-04405426v2⟩
99 Consultations
37 Téléchargements

Altmetric

Partager

More