Misalkan dan dua buah graf. Hasil kali kronecker dan , dilambangkan dengan , adalah graf dengan himpunan titik dan himpunan sisi dan . Konektivitas-titik graf atau adalah minimum banyaknya titik yang harus dihapus agar graf yang baru tak terhubung atau graf trivial. Konektivitas-titik super dari graf , dilambangkan dengan , adalah minimum banyak titik yang dihapus agar graf yang baru tak terhubung dan tidak memuat titik terasing. Jelas bahwa jika graf tak terhubung, maka . Penentuan nilai eksak konektivitas-titik dan konektivitas-titik super hasil kali kronecker dua graf secara umum merupakan permasalahan yang sulit. Dalam artikel ini akan ditunjukkan bahwa , jika dan . Begitu juga, akan ditunjukan , jika graf bipartit dengan dan . Dan ditunjukan juga bahwa , jika dan . Akhirnya, dibuktikan bahwa , jika , , dan . Pembahasan ini akan diawali dengan pembuktian bahwa perkalian kronecker dua graf terhubung merupakan graf terhubung jika dan hanya jika salah satu dari kedua graf tersebut memuat sikel ganjil.
Kata Kunci: konektivitas-titik hasil kali kronecker dua graf, konektivitas-titik super hasil kali kronecker dua graf untuk
beberapa kelas graf tertentu.
Let and be two graphs. Kronecker product of and , denoted by , is a graph with a set of vertex and a set of edge dan . The vertex-connectivity of graph atau is the minimum number of vertex that must be removed so that a new graph is disconnected or a trivial graph. The super connectivity-vertex of graph G, denoted by , are the minimum number of vertex removed so that the new graph is disconnected and does not contain isolated vertexs. It is clear that if graph is disconnected, then . Determining the exact value of connectivity-vertex and super connectivity-vertex kronecker products of two graphs is generally a difficult problem. In this paper it will be shown that , if and . Likewise, it will be shown , if bipartite graphs with and . Finally, it is proved that , if and . This discussion will begin with proof that the kronecker product of two connected graphs is a connected graph if and only if one of the two graphs contains an odd cycle.
Keywords: connectivity-vertex of two graphs, super connectivity-vertex kronecker products of two graphs for some
classes of graph.