STRUKTUR GRAF DENGAN BARISAN DERAJAT  DAN

GRAPH STRUCTURE DEGREE SEQUENCE  AND

 Graf G terdiri atas himpunan titik V(G) dan himpunan sisi E(G). Salah satu aspek penting dalam graf adalah barisan derajat, yaitu representasi derajat titik yang memberikan informasi ringkas tentang karakteristik graf. Penelitian ini mengkaji graf dengan barisan derajat {(m-1)^m,(n-1)^n } yang memiliki m titik masing-masing berderajat m-1 dan n titik masing-masing berderajat n-1. Graf ini ekuivalen-derajat dengan graf komplet K_m∪K_n, tetapi tidak isomorfik dengannya, dilambangkan G_(m,n). Sementara itu, komplemen dari graf ini, yaitu graf G ̅_(m,n) merupakan graf dengan barisan derajat {m^n,n^m }, yang ekuivalen-derajat dengan graf bipartit K_(m,n) tetapi tidak isomorfik dengannya.

Penelitian ini bertujuan untuk mendeskripsikan karakteristik graf dengan barisan derajat tersebut. Hasil analisis menunjukkan bahwa graf ini memiliki sifat keterhubungan, keberadaan titik-pemutus dan sisi-pemutus, serta sifat Hamiltonian, dengan diam(G)≤4 dan bersifat pancyclic. Selain itu, graf ini menunjukkan fleksibilitas melalui operasi pengalihan dua sisi yang dapat menghasilkan graf-graf ekuivalen-derajat. Dengan sifat-sifat tersebut, graf ini memiliki potensi penerapan dalam sistem jaringan komputer, transportasi, dan analisis sosial.

A graph G consist of a set of vetices V(G) and a set of edges E(G). One of essential aspects of a graph is the degree sequence, which represents the degrees of vertices and provides concise information about the graph is characteristics. This study examines graphs with the degree sequence {(m-1)^m,(n-1)^n } where m vertices each have a degree of m-1 and n vertices each have a degree of n-1. This graph is degree-equivalent to the complete graph K_m∪K_n but not isomorphic to it and denoted as G_(m,n). Meanwhile, the complement of this graph, denoted as G ̅_(m,n), has the degree {m^n,n^m }, which is degree-equivalent to bipartite graph K_(m,n) but not isomorphic to it.

This study aims to describe the characteristics of graph with such degree sequence. The analysis result indicate that these graphs exhibit connectivity properties, the presence of cut-vertices and cut-edges, and Hamiltonian properties, with a diameter diam(G)≤4 and pancyclicity. Furthermore, these graphs demonstrate flexibility through the two-switch operation, which can generate degree-equvalent graph. With these properties, these graphs have potential applications in computer networks, transportation systems, and social network analysis.