Counting and labeling grid related graphs
<p>In this work we explore some graphs associated with the grid <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span>. A fence is any subgraph of the grid obtaine...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2019-10-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/753 |
| _version_ | 1811335761199366144 |
|---|---|
| author | Christian Barrientos Sarah Minion |
| author_facet | Christian Barrientos Sarah Minion |
| author_sort | Christian Barrientos |
| collection | DOAJ |
| description | <p>In this work we explore some graphs associated with the grid <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span>. A fence is any subgraph of the grid obtained by deleting any feasible number of edges from some or all the copies of <span class="math"><em>P</em><sub><em>m</em></sub></span>. We present here a closed formula for the number of non-isomorphic fences obtained from <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span>, for every <span class="math"><em>m</em>, <em>n</em> ≥ 2</span>. A rigid grid is a supergraph of the grid, where for every square a pair of opposite vertices are connected; we show that the number of fences built on <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span> is the same that the number of rigid grids built on <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em> + 1</sub></span>. We also introduce a substitution scheme that allows us to substitute any interior edge of any <span class="math"><em>P</em><sub><em>m</em></sub></span> in an <span class="math"><em>α</em></span>-labeled copy of <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span> to obtain a new graph with an <span class="math"><em>α</em></span>-labeling. This process can be iterated multiple times on the <span class="math"><em>n</em></span> copies of <span class="math"><em>P</em><sub><em>m</em></sub></span>; in this way we prove the existence of an <span class="math"><em>α</em></span>-labeling for any graph obtained via these substitutions; these graphs form a quite robust family of <span class="math"><em>α</em></span>-graphs where the grid is one of its members. We also show two subfamilies of disconnected graphs that can be obtained using this scheme, proving in that way that they are also <span class="math"><em>α</em></span>-graphs.</p> |
| first_indexed | 2024-04-13T17:29:49Z |
| format | Article |
| id | doaj.art-ab73c38b7ae94d2db5ba7382a78274dd |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-04-13T17:29:49Z |
| publishDate | 2019-10-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-ab73c38b7ae94d2db5ba7382a78274dd2022-12-22T02:37:37ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872019-10-017234936310.5614/ejgta.2019.7.2.11157Counting and labeling grid related graphsChristian Barrientos0Sarah Minion1Department of Mathematics, Valencia College, East Campus, Orlando, Florida, U.S.A.Department of Mathematics, Full Sail University, Orlando, Florida, U.S.A.<p>In this work we explore some graphs associated with the grid <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span>. A fence is any subgraph of the grid obtained by deleting any feasible number of edges from some or all the copies of <span class="math"><em>P</em><sub><em>m</em></sub></span>. We present here a closed formula for the number of non-isomorphic fences obtained from <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span>, for every <span class="math"><em>m</em>, <em>n</em> ≥ 2</span>. A rigid grid is a supergraph of the grid, where for every square a pair of opposite vertices are connected; we show that the number of fences built on <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span> is the same that the number of rigid grids built on <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em> + 1</sub></span>. We also introduce a substitution scheme that allows us to substitute any interior edge of any <span class="math"><em>P</em><sub><em>m</em></sub></span> in an <span class="math"><em>α</em></span>-labeled copy of <span class="math"><em>P</em><sub><em>m</em></sub> × <em>P</em><sub><em>n</em></sub></span> to obtain a new graph with an <span class="math"><em>α</em></span>-labeling. This process can be iterated multiple times on the <span class="math"><em>n</em></span> copies of <span class="math"><em>P</em><sub><em>m</em></sub></span>; in this way we prove the existence of an <span class="math"><em>α</em></span>-labeling for any graph obtained via these substitutions; these graphs form a quite robust family of <span class="math"><em>α</em></span>-graphs where the grid is one of its members. We also show two subfamilies of disconnected graphs that can be obtained using this scheme, proving in that way that they are also <span class="math"><em>α</em></span>-graphs.</p>https://www.ejgta.org/index.php/ejgta/article/view/753graceful, $\alpha$-labeling, fence, rigid grid |
| spellingShingle | Christian Barrientos Sarah Minion Counting and labeling grid related graphs Electronic Journal of Graph Theory and Applications graceful, $\alpha$-labeling, fence, rigid grid |
| title | Counting and labeling grid related graphs |
| title_full | Counting and labeling grid related graphs |
| title_fullStr | Counting and labeling grid related graphs |
| title_full_unstemmed | Counting and labeling grid related graphs |
| title_short | Counting and labeling grid related graphs |
| title_sort | counting and labeling grid related graphs |
| topic | graceful, $\alpha$-labeling, fence, rigid grid |
| url | https://www.ejgta.org/index.php/ejgta/article/view/753 |
| work_keys_str_mv | AT christianbarrientos countingandlabelinggridrelatedgraphs AT sarahminion countingandlabelinggridrelatedgraphs |