A Collection of Minimally Path Square-Saturated Graphs
Given a simple graph G, m a positive integer. The square of path graph P_m, denoted by P_m^2, is a graph obtained from P_m by adding new edges between any pair of vertices at distance at most 2 in P_m. A graph G is P_m^2-saturated if G does not contain P_m^2 as a subgraph, but the addition of any ed...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
UIN Sunan Gunung Djati Bandung, Mathematics Department
2020-10-01
|
| Series: | Kubik |
| Subjects: | |
| Online Access: | https://journal.uinsgd.ac.id/index.php/kubik/article/view/8415 |
| Summary: | Given a simple graph G, m a positive integer. The square of path graph P_m, denoted by P_m^2, is a graph obtained from P_m by adding new edges between any pair of vertices at distance at most 2 in P_m. A graph G is P_m^2-saturated if G does not contain P_m^2 as a subgraph, but the addition of any edge between two nonadjacent vertices in G contain P_m^2. The minimum size of P_m^2-saturated graph on n vertices is called a saturation number for P_m^2, denoted by sat(n,P_m^2). A set Sat(n,P_m^2 )={G:|V(G)|=sat(n,P_m^2) and G a P_m^2-saturated graph}. All graphs in Sat(n,P_m^2) are obtained computationally for n≤8 and m≤8 and expressed by their degree sequence. |
|---|---|
| ISSN: | 2338-0896 2686-0341 |