pith. sign in

arxiv: 1907.07650 · v1 · pith:PNS6DZUInew · submitted 2019-07-17 · 🧮 math.CO

Independence and Matching Numbers of Unicyclic Graphs From Null Space

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

Pith reviewed 2026-05-24 20:18 UTC · model grok-4.3

classification 🧮 math.CO
keywords unicyclic graphsnull spacesingular graphsindependence numbermatching numberpendant treesadjacency matrix
0
0 comments X

The pith

Unicyclic graphs that are singular are characterized by the support of the null space of their pendant trees, which directly gives closed formulas for independence and matching numbers.

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

The paper establishes a characterization of singular unicyclic graphs by examining the support of the null space associated with their pendant trees. This characterization is then used to derive closed formulas for the independence number and the matching number of any unicyclic graph, expressed in terms of the support of its subtrees. The formulas enable computation of these invariants through linear algebra operations on the graph's adjacency matrix rather than direct combinatorial enumeration. A sympathetic reader would care because independence and matching numbers are core parameters in graph theory with applications in optimization and network analysis, and the approach provides an algebraic route to exact values for this family of graphs.

Core claim

We characterize unicyclic graphs that are singular using the support of the null space of their pendant trees. From this, we obtain closed formulas for the independence and matching numbers of a unicyclic graph, based on the support of its subtrees. These formulas allows one to compute independence and matching numbers of unicyclic graphs using linear algebra methods.

What carries the argument

The support of the null space of pendant trees, which carries the characterization of singularity and supplies the inputs to the closed formulas for independence and matching numbers.

If this is right

  • Independence and matching numbers of unicyclic graphs become computable directly from the null space of the adjacency matrix of their pendant subtrees.
  • Singularity of any unicyclic graph is decided by inspecting only the supports within its pendant trees.
  • The same support data yields both the independence number and the matching number in closed form.
  • Linear algebra methods replace combinatorial search for these two parameters on unicyclic graphs.

Where Pith is reading between the lines

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

  • The method may extend to give algebraic expressions for other nullity-related parameters on unicyclic graphs.
  • Similar support-based formulas could be tested on graphs obtained by attaching cycles to trees in other controlled ways.
  • If the support data can be read off from the cycle length and pendant structure alone, the formulas become fully combinatorial without matrix computation.

Load-bearing premise

The support of the null space of pendant trees provides a complete characterization of singularity for every unicyclic graph and directly yields exact closed formulas for the independence and matching numbers.

What would settle it

A concrete unicyclic graph whose singularity status does not match the support of the null space of its pendant trees, or for which the closed formulas produce values different from the independently computed independence or matching number.

Figures

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

Figure 1
Figure 1. Figure 1: Support, matching and independent set. Definition 2.3. Let G be a graph with n vertices and let x be a vector of R n . The support of x in G is SuppG(x) = {v ∈ V (G) : xv 6= 0}. Let S be a subset of R n . Then the support of S in G is SuppG(S) = [ x∈S SuppG(x). As a convention, we use rectangular vertices in figures to represent vertices of the support. Consider the tree T1 ( [PITH_FULL_IMAGE:figures/full… view at source ↗
Figure 2
Figure 2. Figure 2: Unicyclic graphs of Type I and II and their pendant trees. Definition 3.2. [7] For a tree G{v} with at least two vertices, the vertex v ∈ G{v} is called mismatched in G{v} if there exists a maximum matching of G{v} that does not saturate v; otherwise, v is called matched in G{v}. If a tree consists of only one vertex it is considered mismatched. A unicyclic graph G is said be of Type I if there exists a ve… view at source ↗
Figure 3
Figure 3. Figure 3: Null decomposition of the tree T. Proposition 4.4. Let T be a non-singular tree and v ∈ V (T). Then there exist I1, I2 ∈ I(T) such that v ∈ I1 and v /∈ I2. Proof. Since T is a tree we have that T is a bipartite graph. Then there are two disjoint subsets B1 and B2 of V (T) such that V (T) = B1 ∪B2 and for all {a, b} ∈ E(T) we have {a, b}∩B1 6= ∅ and {a, b}∩B2 6= ∅. As T is a non-singular tree, it has perfec… view at source ↗
Figure 4
Figure 4. Figure 4: Unicyclic graph G and its subtrees. Therefore, by Theorem 4.7, we have that the independence number of G is given by: α(G) = |Supp(G{v})| + |Supp(G − G{v})|+ |V (FN (G{v}))|+|V (FN (G − G{v}))| 2 = 3 + 5 + 2 2 = 9. We observe that J = {a, b, c, d, e, g, i, j, c} is a maximum independent set of G and |J| = 9. Lemma 4.8. Let G be a unicyclic graph and C its cycle. Let G{v} be a pendant tree such that v ∈ Sup… view at source ↗
Figure 5
Figure 5. Figure 5: Unicyclic graph of Type II and the support of its subtrees. As an example, consider G the unicyclic graph of [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: M-alternating path and M-augmenting path. The following is a classic result, it characterizes maximum matchings in a graph G. Lemma 5.2. (Berge, 1957)[4] A matching M is maximum in G if and only if G does not have an M-augmenting path. We now give a closed formula for the matching number of unicyclic graphs G of Type I. This formula depends on the core and N-vertices of subtrees. Theorem 5.3. If G is a uni… view at source ↗
Figure 7
Figure 7. Figure 7: M-augmenting path P. Let B1 = {{a2k, v}, {u, b1}} ∪ k S−1 i=1 {{a2i , a2i+1}} ∪ sS−1 j=1 {{b2j , b2j+1}} and B2 = {{u, v}} ∪ S k i=1 {{a2i−1, a2i}} ∪ Ss j=1 {{b2j−1, b2j}}. We observe that B1 ⊆ M and B2 ∩ M = ∅. Let M′ be a matching in G given by M′ = (M ∪ B2) \ B1. As M ′ ∩ E(G{v}) is a matching in G{v}, we see that it does not saturate v, because v /∈ Supp(G{v}). Hence M ′ ∩ E(G{v}) ∈ M/ (G{v}) (see Lemm… view at source ↗
Figure 8
Figure 8. Figure 8: Unicyclic graph of Type I and support of subtrees. Therefore, by Theorem 5.3, we have that the matching number of G is given by ν(G) = |Core(G{v})|+|Core(G − G{v})|+ |V (FN (G{v}))| + |V (FN (G − G{v}))| 2 = 1 + 4 2 + 2 + 2 2 = 6. We point out that M = {{b, c}, {v, d}, {ℓ, m}, {n, o}, {e, g}, {f, h}} is a maximum matching of G and |M| = 6. We now present a similar result for the matching number of unicycli… view at source ↗
Figure 9
Figure 9. Figure 9: Unicyclic graph of Type II and its subtrees T1, T2, T3 and T4. Acknowledgments Work supported by MATHAMSUD 18-MATH-01. Maikon Toledo thanks CAPES for their support. V. Trevisan acknowledges partial support of CNPq grants 409746/2016-9 and 303334/2016-9, and FAPERGS (Proj. PqG 17/2551-0001). References [1] N. Alon and R. B. Boppana. The Monotone Circuit Complexity of Boolean Functions. Combina￾torica, 7:1-2… view at source ↗
read the original abstract

We characterize unicyclic graphs that are singular using the support of the null space of their pendant trees. From this, we obtain closed formulas for the independence and matching numbers of a unicyclic graph, based on the support of its subtrees. These formulas allows one to compute independence and matching numbers of unicyclic graphs using linear algebra methods.

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

1 major / 1 minor

Summary. The paper claims to characterize singular unicyclic graphs using the support of the null space of their pendant trees. From this characterization, it derives closed formulas for the independence number α(G) and matching number ν(G) of a unicyclic graph based on the support of its subtrees. These formulas are presented as allowing computation of the invariants via linear algebra methods.

Significance. If the claimed characterization and formulas hold without gaps, the work would establish a direct reduction from the combinatorial parameters of unicyclic graphs to the nullspace supports of attached trees, providing an explicit linear-algebraic route to α(G) and ν(G) that avoids standard combinatorial search. This would be a useful contribution in spectral graph theory for the class of unicyclic graphs.

major comments (1)
  1. [Abstract] Abstract (first two sentences): the central claim that the support of the nullspace of each pendant tree completely determines singularity of the full unicyclic graph (nullity(A(G)) > 0) and directly supplies exact closed-form expressions for α(G) and ν(G) is load-bearing; the abstract provides no indication that cycle-induced kernel vectors orthogonal to pendant extensions have been ruled out, leaving open whether the reduction is valid for all cycle lengths and attachment configurations.
minor comments (1)
  1. [Abstract] Abstract: 'These formulas allows one' contains a subject-verb agreement error.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed reading of the manuscript. Below we respond point by point to the single major comment.

read point-by-point responses

  1. Referee: [Abstract] Abstract (first two sentences): the central claim that the support of the nullspace of each pendant tree completely determines singularity of the full unicyclic graph (nullity(A(G)) > 0) and directly supplies exact closed-form expressions for α(G) and ν(G) is load-bearing; the abstract provides no indication that cycle-induced kernel vectors orthogonal to pendant extensions have been ruled out, leaving open whether the reduction is valid for all cycle lengths and attachment configurations.

    Authors: The manuscript's core results (Theorems 3.1 and 4.2 together with the supporting lemmas in Section 3) establish that the nullity of any unicyclic graph is completely determined by the supports of the nullspaces of its pendant trees; the proofs explicitly demonstrate that no additional linearly independent kernel vectors arise from the cycle itself, for every cycle length and every possible attachment configuration of the trees. The abstract is intentionally concise and therefore omits the proof strategy, but the reduction is shown to be valid without exception. We agree that a brief clarifying phrase in the abstract would make the scope of the claim more transparent to readers. revision: partial

Circularity Check

0 steps flagged

No circularity: derivation relies on independent linear-algebraic characterization

full rationale

The abstract and available description present a characterization of singular unicyclic graphs via the support of the nullspace of pendant trees, followed by closed formulas for independence and matching numbers derived from that support. No quoted equations, definitions, or steps reduce the target quantities (nullity, α(G), ν(G)) to fitted parameters, self-referential definitions, or load-bearing self-citations. The approach uses standard spectral properties of the adjacency matrix on trees and their attachments; these are external to the claimed formulas and do not collapse by construction. The derivation is therefore self-contained against the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no concrete list of free parameters, axioms, or invented entities; the work appears to rest on standard linear-algebra facts about null spaces and graph matrices.

pith-pipeline@v0.9.0 · 5580 in / 999 out tokens · 20547 ms · 2026-05-24T20:18:23.401255+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

13 extracted references · 13 canonical work pages

  1. [1]

    Alon and R

    N. Alon and R. B. Boppana. The Monotone Circuit Complexity of Boo lean Functions. Combina- torica, 7:1-22, 1987

    work page 1987

  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]

    R. B. Bapat. Graph and Matrices. In Universitext. SBMAC- Springer, 2010. ISBN: 978-1-84882- 980-0

    work page 2010

  4. [4]

    C. Berge. Two theorems in graph theory. Proceedings of the Na tional Academy of Sciences 43(9): 842-844, 1957

    work page 1957

  5. [5]

    D. M. Cvetkov´ c, M. Doob and H. Sachs. Spectra of graphs: th eory and application, vol. 87. Academic Pr, 1980

    work page 1980

  6. [6]

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

    work page 1990

  7. [7]

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

    work page 2010

  8. [8]

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

    work page 2018

  9. [9]

    R. M. Karp. Reducibility among combinatorial problems. In: Miller R.E ., Thatcher J.W., Bohlinger J.D. (eds) Complexity of Computer Computations , The IBM Research Symposia Se- ries. Springer, 85-103, 1972

    work page 1972

  10. [10]

    D. K¨ onig. Gr´ afok ´ es alkalmaz´ asuk a determin´ ansok ´ es a h almazok, Matematikai ´ ss Term´ eszettudom´ anyi´Ertes ´ ıt¨ o, 34:104119, 1916

    work page 1916

  11. [11]

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

    work page 2001

  12. [12]

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

    work page 1983

  13. [13]

    Sookyang, S

    S. Sookyang, S. Arworn and P. Wojtylak. Characterizations o f Non-Singular Cycles, Path and Trees. Thai Journal of Mathematics , 6:331-336, 2008. E-mail address : emilio.allem@ufrgs.br INDEPENDENCE AND MATCHING NUMBERS OF UNICYCLIC GRAPHS FROM NULL SPACE 17 UFRGS - Universidade Federal do Rio Grande do Sul, Instituto de Matem ´atica, Porto Alegre, Brazil ...

    work page 2008