Rank of signed cacti
A signed cactus \(\dot{G}\) is a connected signed graph such that every edge belongs to at most one cycle. The rank of \(\dot{G}\) is the rank of its adjacency matrix. In this paper we prove that \[\sum_{i=1}^k n_i-2k\leq \operatorname{rank}(\dot{G})\leq \sum_{i=1}^k n_i-2t +2 s,\] where \(k\) is t...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Journal of Combinatorics
2023-10-01
|
| Series: | The American Journal of Combinatorics |
| Subjects: | |
| Online Access: | https://ajcombinatorics.org/ojs/index.php/AmJC/article/view/13 |
| _version_ | 1826585463979245568 |
|---|---|
| author | Zoran Stanić |
| author_facet | Zoran Stanić |
| author_sort | Zoran Stanić |
| collection | DOAJ |
| description |
A signed cactus \(\dot{G}\) is a connected signed graph such that every edge belongs to at most one cycle. The rank of \(\dot{G}\) is the rank of its adjacency matrix. In this paper we prove that \[\sum_{i=1}^k n_i-2k\leq \operatorname{rank}(\dot{G})\leq \sum_{i=1}^k n_i-2t +2 s,\] where \(k\) is the number of cycles in \(\dot{G}\), \(n_1, n_2, \ldots, n_k\) are their lengths, \(t\) is the number of cycles whose rank is their order minus two, and \(s\) is the number of edges outside cycles. Signed cacti attaining the lower bound are determined.
|
| first_indexed | 2025-03-14T15:54:03Z |
| format | Article |
| id | doaj.art-5b980836b6e84e7b810255ce3bc78de5 |
| institution | Directory Open Access Journal |
| issn | 2768-4202 |
| language | English |
| last_indexed | 2025-03-14T15:54:03Z |
| publishDate | 2023-10-01 |
| publisher | American Journal of Combinatorics |
| record_format | Article |
| series | The American Journal of Combinatorics |
| spelling | doaj.art-5b980836b6e84e7b810255ce3bc78de52025-02-24T02:28:16ZengAmerican Journal of CombinatoricsThe American Journal of Combinatorics2768-42022023-10-01210.63151/amjc.v2i.13Rank of signed cactiZoran Stanić A signed cactus \(\dot{G}\) is a connected signed graph such that every edge belongs to at most one cycle. The rank of \(\dot{G}\) is the rank of its adjacency matrix. In this paper we prove that \[\sum_{i=1}^k n_i-2k\leq \operatorname{rank}(\dot{G})\leq \sum_{i=1}^k n_i-2t +2 s,\] where \(k\) is the number of cycles in \(\dot{G}\), \(n_1, n_2, \ldots, n_k\) are their lengths, \(t\) is the number of cycles whose rank is their order minus two, and \(s\) is the number of edges outside cycles. Signed cacti attaining the lower bound are determined. https://ajcombinatorics.org/ojs/index.php/AmJC/article/view/13Adjacency matrixTree-like signed graphRankCycle |
| spellingShingle | Zoran Stanić Rank of signed cacti The American Journal of Combinatorics Adjacency matrix Tree-like signed graph Rank Cycle |
| title | Rank of signed cacti |
| title_full | Rank of signed cacti |
| title_fullStr | Rank of signed cacti |
| title_full_unstemmed | Rank of signed cacti |
| title_short | Rank of signed cacti |
| title_sort | rank of signed cacti |
| topic | Adjacency matrix Tree-like signed graph Rank Cycle |
| url | https://ajcombinatorics.org/ojs/index.php/AmJC/article/view/13 |
| work_keys_str_mv | AT zoranstanic rankofsignedcacti |