We pursue the study of edge-irregulators of graphs, which were recently introduced in [Fioravantes et al. Parametrised Distance to Local Irregularity. IPEC, 2024]. That is, we are interested in the parameter \(\textrm{I}_e(G)\) , which, for a given graph G, denotes the smallest \(k \ge 0\) such that G can be made locally irregular (i.e., with no two adjacent vertices having the same degree) by deleting k edges. We exhibit notable properties of interest of the parameter \(\textrm{I}_e\) , in general and for particular classes of graphs, together with parameterized algorithms for several natural graph parameters. Despite the computational hardness previously exhibited by this problem (NP-hard, W[1]-hard w.r.t. feedback vertex number, W[1]-hard w.r.t. solution size), we present two FPT algorithms, the first w.r.t. the solution size plus \(\varDelta \) and the second w.r.t. the vertex cover number of the input graph. Finally, we take important steps towards better understanding the behaviour of this problem in dense graphs. This is crucial when considering some of the parameters whose behaviour is still uncharted in regards to this problem (e.g., neighbourhood diversity, distance to clique). In particular, we identify a sub-family of complete graphs for which we are able to provide the exact value of \(\textrm{I}_e(G)\) . These investigations lead us to propose a conjecture that \(\textrm{I}_e(G)\) should always be at most \(\frac{1}{3}m+c\) , where m is the number of edges of the graph G and c is some constant. This conjecture is verified for various families of graphs, including trees.

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

Graph Irregularity via Edge Deletions

  • Julien Bensmail,
  • Noëmie Catherinot,
  • Foivos Fioravantes,
  • Clara Marcille,
  • Nacim Oijid

摘要

We pursue the study of edge-irregulators of graphs, which were recently introduced in [Fioravantes et al. Parametrised Distance to Local Irregularity. IPEC, 2024]. That is, we are interested in the parameter \(\textrm{I}_e(G)\) , which, for a given graph G, denotes the smallest \(k \ge 0\) such that G can be made locally irregular (i.e., with no two adjacent vertices having the same degree) by deleting k edges. We exhibit notable properties of interest of the parameter \(\textrm{I}_e\) , in general and for particular classes of graphs, together with parameterized algorithms for several natural graph parameters. Despite the computational hardness previously exhibited by this problem (NP-hard, W[1]-hard w.r.t. feedback vertex number, W[1]-hard w.r.t. solution size), we present two FPT algorithms, the first w.r.t. the solution size plus \(\varDelta \) and the second w.r.t. the vertex cover number of the input graph. Finally, we take important steps towards better understanding the behaviour of this problem in dense graphs. This is crucial when considering some of the parameters whose behaviour is still uncharted in regards to this problem (e.g., neighbourhood diversity, distance to clique). In particular, we identify a sub-family of complete graphs for which we are able to provide the exact value of \(\textrm{I}_e(G)\) . These investigations lead us to propose a conjecture that \(\textrm{I}_e(G)\) should always be at most \(\frac{1}{3}m+c\) , where m is the number of edges of the graph G and c is some constant. This conjecture is verified for various families of graphs, including trees.