Antimagic valuations and complexity of graphs
| dc.contributor.author | Hafiz Usman Afzal | |
| dc.date.accessioned | 2025-11-28T21:06:53Z | |
| dc.date.available | 2025-11-28T21:06:53Z | |
| dc.date.issued | 2024-03-13 | |
| dc.description.abstract | A bijection that assigns the elements of a graph, i.e., vertices, edges or both the non-negative integers, is known as valuation. The aforesaid valuations are referred as vertex, edge or total valuations on graphs, respectively. In particular, total valuation is our consideration, in which the sum of labels of a pair of vertices and edge incident upon is constant, throughout the graph, is called edge-magic total valuation. If the smallest non-negative integers are assigned to vertices of a graph, then the same valuation is referred as a super edge-magic total valuation. A super valuation in which edge-weights constitute a progression which is arithmetic, with common difference d and minimum edge-weight a, is termed as super (a, d)-edge antimagic total valuation. The former part of our research dissertation concerns with the development of super (a, d)-edge antimagic total valuations of various classes of graphs, for various values of d. These classes include Usmanian Ladders, tri-parametric family of pancyclic graphs named as Usmaninan Pancyclic graphs, symmetric lattices containing chains of tripartite graphs named as Hexagonal Lattice, Prismatic Lattice, Diatom Lattice and Pyramidion Lattice. The aforementioned valuation has also been designed on the rooted product of cycle Cn and Pn with a pancyclic graph. This portion further contains the disjoint union of rooted products Pn ◦ K2,n, Cn ◦ K2,n and various classes of trees. The latter part of our dissertation concerns with the computation of the complexity of various graph operations. Preliminarily, a spanning tree of a graph G is a subgraph of G that is itself a tree and contains every vertex of G. The total number of distinct spanning trees of a graph G is known as its complexity, denoted by τ (G). The foremost of the results on complexity includes the determination of the complexity function of the complete graph Kn as τ (Kn) = nn−2 and the complete bipartite graph Km,n as τ (Km,n) = mn−1nm−1. These formulae were discovered by G. A. Cayley in 1889, using algorithmic techniques. We will derive the closed formulae for the complexity of the generalized operation such as shadow, switch, split, mirror, sum, various products, symmetric difference, disjunction and conjunction of various families of graphs. More importantly, our approach will be algebraic for the derivation of these results, instead of algorithmic. | |
| dc.identifier.uri | https://escholar.umt.edu.pk/handle/123456789/13588 | |
| dc.language.iso | en | |
| dc.publisher | UMT Lahore | |
| dc.title | Antimagic valuations and complexity of graphs | |
| dc.type | Thesis |
Files
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- Antimagic valuations and complexity of graphs.pdf
- Size:
- 9.92 MB
- Format:
- Adobe Portable Document Format
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: