pith. sign in

arxiv: 1907.08618 · v1 · pith:HSYWRNWOnew · submitted 2019-07-19 · 🧮 math.CO

Null Decomposition of Unicyclic Graphs

Luiz Emilio Allem , Daniel Alejandro Jaume , Gonzalo Molina , Maikon Machado Toledo , Vilmar Trevisan This is my paper

Pith reviewed 2026-05-24 19:31 UTC · model grok-4.3

classification 🧮 math.CO
keywords unicyclic graphsnull spacenull decompositionindependence numbermatching numbersupport
0
0 comments X

The pith

Unicyclic graphs have an explicit basis for their null space obtained by extending the tree decomposition.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to extend the null decomposition method from trees to unicyclic graphs, which contain a single cycle. This extension produces a concrete basis for the null space of these graphs. Using this basis, the authors derive closed formulas for the independence number and the matching number that depend only on the support of the graph. This approach avoids direct computation of maximum independent sets or matchings and instead reads the values from the vertices that participate in null vectors.

Core claim

By extending the null decomposition of trees, unicyclic graphs admit a basis for the null space, from which closed formulas for the independence and matching numbers are obtained directly from the support of the graph.

What carries the argument

The null decomposition, a structural partition that identifies the vertices in the support and constructs the null vectors explicitly.

If this is right

  • Independence numbers of unicyclic graphs are given by closed formulas based on the support.
  • Matching numbers of unicyclic graphs are given by closed formulas based on the support.
  • The null space basis is constructed explicitly from the decomposition.
  • The dimension of the null space is determined by the cycle and pendant structures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method could extend to graphs with few cycles.
  • Support might be useful for other spectral invariants in unicyclic graphs.
  • Algorithms could prioritize support computation for efficiency.

Load-bearing premise

The structural decomposition used for trees carries over to the single-cycle case without introducing new dependencies that would invalidate the explicit basis or the support-based formulas.

What would settle it

A specific unicyclic graph where the formula for the independence number from the support disagrees with the known value.

Figures

Figures reproduced from arXiv: 1907.08618 by Daniel Alejandro Jaume, Gonzalo Molina, Luiz Emilio Allem, Maikon Machado Toledo, Vilmar Trevisan.

Figure 1
Figure 1. Figure 1: Unicyclic graph G and its support. Notice that, V (C) * V (GN (G)). Therefore, by theorems 7.10 and 7.13, we have that the independence and matching numbers of G can be computed as follows α(G) = |Supp(G)|+  |V (GN (G))| − |Supp(G) ∩ Core(G)| 2  = 5 +  9 − 0 2  = 10 ν(G) = |Core(G)|+  |V (GN (G))| − |Supp(G) ∩ Core(G)| 2  = 4 +  9 − 0 2  = 8. Our main goal in this paper is to extend the theory that… view at source ↗
Figure 2
Figure 2. Figure 2: Unicyclic graph whose support is not an independent set. The next stated result shows that only the vertices of the support of a tree are not saturated by some maximum matching. Lemma 2.4. [1] Let T be a tree, then EG(T) = Supp(T). Let G be a unicyclic graph and let C be the unique cycle of G. For each vertex v ∈ V (C), we denote by G{v} the induced connected subgraph of G with maximum number of vertices, … view at source ↗
Figure 3
Figure 3. Figure 3: Null decomposition of the unicyclic graph G. The unicyclic graph G in [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Unicyclic graph G its support. In the next example, we use the theorems 7.10 and 7.13 to obtain α(G) and ν(G) of the unicyclic graph G in [PITH_FULL_IMAGE:figures/full_fig_p027_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Unicyclic graph G and its support. Notice that V (C) * V (GN (G)). Therefore, by theorems 7.10 and 7.13, we have that the independence and matching numbers of G are given by α(G) = |Supp(G)|+  |V (GN (G))| − |Supp(G) ∩ Core(G)| 2  = 10 +  2 − 4 2  = 9 ν(G) = |Core(G)|+  |V (GN (G))| − |Supp(G) ∩ Core(G)| 2  = 7 +  2 − 4 2  = 6. Observe that I = {b, c, d, e, g, j, ℓ, v, z} ∈ I(G) and M = {{a, b}, {e… view at source ↗
read the original abstract

In this work we obtain basis for the null space of unicyclic graphs. We extend the null decomposition of trees from [11] for unicyclic graphs. As an application, we obtain closed formulas for the independence and matching numbers of unicyclic graphs just using the support of the graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims to construct an explicit basis for the nullspace of the adjacency matrix of unicyclic graphs by extending the null decomposition previously developed for trees. It further derives closed-form expressions for the independence number and matching number that depend only on the support of the graph.

Significance. If the extension is valid, the work supplies a direct combinatorial description of the kernel for graphs containing exactly one cycle and yields parameter-free formulas for two fundamental invariants, building on the tree case in [11].

major comments (2)
  1. [basis construction for unicyclic graphs] The central extension step must verify that the cycle does not introduce new linear dependencies among the proposed basis vectors. The manuscript should contain an explicit argument (likely in the section presenting the basis construction) showing that the vectors remain independent when the cycle is adjoined to the tree components, addressing possible even/odd length relations.
  2. [application to independence and matching numbers] The closed formulas for independence and matching numbers rely on the support coinciding with the tree case. The paper needs to prove that the support is unaffected by the cycle (or precisely how it changes), as any shift would invalidate the formulas; this should be stated as a separate lemma with a direct check on the cycle vertices.
minor comments (1)
  1. Notation for the support set and the basis vectors should be made uniform across the tree and unicyclic cases to facilitate comparison with [11].

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points where additional explicit arguments are needed to strengthen the manuscript. We address each major comment below and will incorporate the requested clarifications and lemmas in the revised version.

read point-by-point responses

  1. Referee: [basis construction for unicyclic graphs] The central extension step must verify that the cycle does not introduce new linear dependencies among the proposed basis vectors. The manuscript should contain an explicit argument (likely in the section presenting the basis construction) showing that the vectors remain independent when the cycle is adjoined to the tree components, addressing possible even/odd length relations.

    Authors: We agree that an explicit verification of linear independence is required when adjoining the cycle. The original construction extends the tree case by defining vectors on the cycle vertices in a manner that preserves the kernel property, but we acknowledge the need for a dedicated argument covering even- and odd-length cycles to rule out new dependencies. In the revised manuscript we will insert a new lemma (placed immediately after the basis construction) that proves independence by direct linear combination analysis, handling the two parity cases separately and showing that any dependence relation would contradict the tree-component independence already established in [11]. revision: yes

  2. Referee: [application to independence and matching numbers] The closed formulas for independence and matching numbers rely on the support coinciding with the tree case. The paper needs to prove that the support is unaffected by the cycle (or precisely how it changes), as any shift would invalidate the formulas; this should be stated as a separate lemma with a direct check on the cycle vertices.

    Authors: We accept that the formulas' validity hinges on the support being unchanged by the cycle and that this must be proved explicitly rather than left implicit. We will add a short, self-contained lemma (positioned before the applications section) that performs a direct case analysis on the cycle vertices: for each vertex on the cycle we verify that its membership in the support is identical to the value obtained by treating the cycle as a path (consistent with the tree decomposition). The lemma will also note that no shift occurs because the null-decomposition rule on the cycle is chosen to match the tree rule at the attachment points. revision: yes

Circularity Check

0 steps flagged

No circularity: direct constructive extension of tree nullspace basis to unicyclic case

full rationale

The paper's core contribution is an explicit construction of a nullspace basis for unicyclic graphs that extends the tree case from the cited reference [11]. This extension is presented via direct structural arguments on the cycle and pendant paths rather than by redefining quantities in terms of themselves or by renaming fitted parameters as predictions. The independence and matching number formulas are derived from the support of this basis, which is constructed in the present work. The single citation to prior tree results supplies background but does not carry the load of the unicyclic claims; those claims rest on the new decomposition and are externally falsifiable by linear algebra on the adjacency matrix. No self-definitional loops, ansatz smuggling, or uniqueness theorems imported from the same authors appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; the work is presented as a direct structural extension.

pith-pipeline@v0.9.0 · 5565 in / 987 out tokens · 21677 ms · 2026-05-24T19:31:30.276743+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    L. E. Allem, D. A. Jaume, G. Molina, M. M. Toledo, and V. Trevisan, I ndependence and Matching Numbers of Unicyclic Graphs From Null Space. submitted

    work page

  2. [2]

    Alon and N

    N. Alon and N. Kahale. Approximating the Independence Number v ia the J -function. Mathe- matical Programming, 80:253-264, 1998

    work page 1998

  3. [3]

    Bapat, A

    R. Bapat, A. Lal, and S. Pati, On algebraic connectivity of graphs with at most two points of articulation in each block. Linear and Multilinear Algebra 60, 4, 415432 , 2012. 28 L. E. ALLEM, D. A. JAUME, G. MOLINA, M. M. TOLEDO, AND V. TREV ISAN

    work page 2012

  4. [4]

    D. M. Cvetkovi´ c, M. Doob and H. Sachs. Spectra of graphs: t heory and application, vol. 87. Academic Pr, 1980

    work page 1980

  5. [5]

    J. Edmonds. Paths, trees, and flowers. Canadian Journal of m athematics, 17(3), 449-467, 1965

    work page 1965

  6. [6]

    J. Farr, M. Khatirinejad, S. Khodadad, M. Monagan, A graph th eory package for Maple. In Proceedings of the 2005 Maple Conference, 260-271, 2005

    work page 2005

  7. [7]

    Fiedler, Algebraic connectivity of graphs, Czechoslovak Math ematical Journal, Vol

    M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math ematical Journal, Vol. 23:298-305, 1973

    work page 1973

  8. [8]

    Fiedler, A property of eigenvectors of nonnegative symmetr ic matrices and its application to graph theory, Czechoslovak Mathematical Journal, Vol

    M. Fiedler, A property of eigenvectors of nonnegative symmetr ic matrices and its application to graph theory, Czechoslovak Mathematical Journal, Vol. 25 No. 4:6 19-633, 1975

    work page 1975

  9. [9]

    A. M. Frieze. On the Independence Number of Random Graphs. Discrete Mathematics , 81:171- 175, 1990

    work page 1990

  10. [10]

    S. Gong, Y. Fan and Z. Yin. On the nullity os graphs with pendant t rees. Linear Algebra and its Applications, 433:1374-1380, 2010

    work page 2010

  11. [11]

    D. A. Jaume and G. Molina. Null Decomposition of Trees. Discrete Mathematics , 341:836-850, 2018

    work page 2018

  12. [12]

    G. J. Ming, and T. S. Wang, A relation between the matching numb er and laplacian spectrum of a graph. Linear Algebra and its Applications 325, 1-3, 71-74, 2001

    work page 2001

  13. [13]

    Nikiforov, The influence of Miroslav Fiedler on spectral graph theory, Linear Algebra and Its Applications, Vol

    M. Nikiforov, The influence of Miroslav Fiedler on spectral graph theory, Linear Algebra and Its Applications, Vol. 439: 818-821, 2013

    work page 2013

  14. [14]

    Nylen, Null space structure of tree-patterned matrices

    P. Nylen, Null space structure of tree-patterned matrices. Linear algebra and its applications 279.1-3 :153-161, 1998

    work page 1998

  15. [15]

    D. L. Powers, Graph partitioning by eigenvectors. Linear Algebra and its Applications 101, 121- 133, 1988

    work page 1988

  16. [16]

    J. B. Shearer. A note on the independence number of triangle- free graphs. Discrete Mathematics, 46:83-87, 1983

    work page 1983

  17. [17]

    Xuezhong, and B

    T. Xuezhong, and B. Liu. On the nullity of unicyclic graphs. Linear algebra and its applications 408: 212-220, 2005

    work page 2005

  18. [18]

    Sage Reference Manual: Graph Theory Release 8.5 E-mail address : emilio.allem@ufrgs.br UFRGS - Universidade Federal do Rio Grande do Sul, Instituto de Matem ´atica, Porto Alegre, Brazil E-mail address : djaume@unsl.edu.ar Universidad Nacional de San Luis, Departamento de Matem ´aticas, San Luis, Ar- gentina E-mail address : lgmolina@unsl.edu.ar Universida...

    work page