Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2512.09096 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914622472192000 |
|---|---|
| author | Moxley, Rowan |
| author_facet | Moxley, Rowan |
| contents | We study a conductance-weighted arboricity $A_c(G)$ for a finite simple undirected graph $G=(V,E,c)$ with a conductance assignment $c:E\to(0,\infty)$. This functional reduces to the fractional arboricity $γ(G)$ when $c\equiv 1$, is isomorphism invariant, monotone under taking subgraphs and adding edges, positively homogeneous, and convex. We also prove sharp global bounds with attainment at a connected subgraph. On the analytic side, we introduce a local variant and derive conductance--resistance inequalities using effective resistances in the ambient network, which in turn yields an upper bound and hence an explicit effective resistance-based upper bound on $A_c(G)$. On the structural side, we describe the algebraic behavior of $A_c(G)$. We show that under edge-disjoint unions of graphs, $A_c(G)$ behaves as a max invariant: for a finite disjoint union of weighted graphs one has $A_c(G)= \max_i A_{c_i}(G_i)$. In particular, disjoint union induces a commutative idempotent monoid structure at the level of isomorphism classes, with $A_c(G)$ idempotent with respect to this operation. We also provide a computational exhibit on the hypercube family $Q_d$, including random conductance sampling, illustrating numerical evaluation of the resulting resistance-based bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_09096 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Extensions of Real-Weighted Fractional Arboricity Moxley, Rowan Combinatorics 05C05, 05C42, 05C21, 05C22, 90C35 We study a conductance-weighted arboricity $A_c(G)$ for a finite simple undirected graph $G=(V,E,c)$ with a conductance assignment $c:E\to(0,\infty)$. This functional reduces to the fractional arboricity $γ(G)$ when $c\equiv 1$, is isomorphism invariant, monotone under taking subgraphs and adding edges, positively homogeneous, and convex. We also prove sharp global bounds with attainment at a connected subgraph. On the analytic side, we introduce a local variant and derive conductance--resistance inequalities using effective resistances in the ambient network, which in turn yields an upper bound and hence an explicit effective resistance-based upper bound on $A_c(G)$. On the structural side, we describe the algebraic behavior of $A_c(G)$. We show that under edge-disjoint unions of graphs, $A_c(G)$ behaves as a max invariant: for a finite disjoint union of weighted graphs one has $A_c(G)= \max_i A_{c_i}(G_i)$. In particular, disjoint union induces a commutative idempotent monoid structure at the level of isomorphism classes, with $A_c(G)$ idempotent with respect to this operation. We also provide a computational exhibit on the hypercube family $Q_d$, including random conductance sampling, illustrating numerical evaluation of the resulting resistance-based bound. |
| title | Extensions of Real-Weighted Fractional Arboricity |
| topic | Combinatorics 05C05, 05C42, 05C21, 05C22, 90C35 |
| url | https://arxiv.org/abs/2512.09096 |