Strongly i-Bicritical Graphs
A graph $G$ is \emph{strongly $i$-bicritical} if it has independent domination number $i(G) \geq 3$, and $i(G - \{x, y\}) = i(G) - 2$ whenever $x$ and $y$ are two non-adjacent vertices of $G$. We describe five constructions of strongly $i$-bicritical graphs. For four of them, necessary and sufficien...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Georgia Southern University
2024-01-01
|
| Series: | Theory and Applications of Graphs |
| Subjects: | |
| Online Access: | https://digitalcommons.georgiasouthern.edu/tag/vol11/iss1/2/ |
| _version_ | 1797263113214492672 |
|---|---|
| author | Michelle Edwards Gary MacGillivray Shahla Nasserasr |
| author_facet | Michelle Edwards Gary MacGillivray Shahla Nasserasr |
| author_sort | Michelle Edwards |
| collection | DOAJ |
| description | A graph $G$ is \emph{strongly $i$-bicritical} if it has independent domination number $i(G) \geq 3$, and $i(G - \{x, y\}) = i(G) - 2$ whenever $x$ and $y$ are two non-adjacent vertices of $G$. We describe five constructions of strongly $i$-bicritical graphs. For four of them, necessary and sufficient conditions for the graph produced by the construction to be strongly $i$-bicritical are given. The strongly $i$-bicritical graphs with independent domination number $i(G) = 3$ are characterized, and it is shown that the strongly $i$-bicritical graphs with independent domination number $i(G) \geq 5$ may be hard to characterize. It is shown that every strongly $i$-bicritical graph has minimum degree 3 and is 2-connected. Further, the vertices in any 2-vertex cut must be adjacent. The diameter of a strongly $i$-bicritical graph $G$ is shown to be at most $3i(G) / 2 + 2$. |
| first_indexed | 2024-04-25T00:07:50Z |
| format | Article |
| id | doaj.art-42dfab092d1c4b2a91b865d6209f3eb2 |
| institution | Directory Open Access Journal |
| issn | 2470-9859 |
| language | English |
| last_indexed | 2024-04-25T00:07:50Z |
| publishDate | 2024-01-01 |
| publisher | Georgia Southern University |
| record_format | Article |
| series | Theory and Applications of Graphs |
| spelling | doaj.art-42dfab092d1c4b2a91b865d6209f3eb22024-03-13T17:31:11ZengGeorgia Southern UniversityTheory and Applications of Graphs2470-98592024-01-0111111610.20429/tag.2024.110102Strongly i-Bicritical GraphsMichelle EdwardsGary MacGillivrayShahla NasserasrA graph $G$ is \emph{strongly $i$-bicritical} if it has independent domination number $i(G) \geq 3$, and $i(G - \{x, y\}) = i(G) - 2$ whenever $x$ and $y$ are two non-adjacent vertices of $G$. We describe five constructions of strongly $i$-bicritical graphs. For four of them, necessary and sufficient conditions for the graph produced by the construction to be strongly $i$-bicritical are given. The strongly $i$-bicritical graphs with independent domination number $i(G) = 3$ are characterized, and it is shown that the strongly $i$-bicritical graphs with independent domination number $i(G) \geq 5$ may be hard to characterize. It is shown that every strongly $i$-bicritical graph has minimum degree 3 and is 2-connected. Further, the vertices in any 2-vertex cut must be adjacent. The diameter of a strongly $i$-bicritical graph $G$ is shown to be at most $3i(G) / 2 + 2$.https://digitalcommons.georgiasouthern.edu/tag/vol11/iss1/2/independent dominationindependent domination critical graph |
| spellingShingle | Michelle Edwards Gary MacGillivray Shahla Nasserasr Strongly i-Bicritical Graphs Theory and Applications of Graphs independent domination independent domination critical graph |
| title | Strongly i-Bicritical Graphs |
| title_full | Strongly i-Bicritical Graphs |
| title_fullStr | Strongly i-Bicritical Graphs |
| title_full_unstemmed | Strongly i-Bicritical Graphs |
| title_short | Strongly i-Bicritical Graphs |
| title_sort | strongly i bicritical graphs |
| topic | independent domination independent domination critical graph |
| url | https://digitalcommons.georgiasouthern.edu/tag/vol11/iss1/2/ |
| work_keys_str_mv | AT michelleedwards stronglyibicriticalgraphs AT garymacgillivray stronglyibicriticalgraphs AT shahlanasserasr stronglyibicriticalgraphs |