Choosing Friends in Everyday Life by using Graph Theory

1. Introduction

Graph theory has wide applications in different fields of our routine life. For example, finding shortest route on Google maps, analyzing electrocardiogram (ECG)of a cardiac patient, managing security in housing societies, connecting people with Facebook and Whatsapp, handling transportation system etc. In this article, writers are focussing on applying the subtopic of graph theory, that is, face irregularity strength, to different daily routines of everyday life where six or more components (including people) will be attached. Mathematical graphs which are under consideration in this study are wheel graphs with six or more vertices. Writers have applied a similar application on a school with nine busses. After the successful application of this system, authors realized to publish it for the people around. All graphs $G(V,E,F)$ in this article are simple, finite, plane and undirected. A wheel graph $W_n$ with $n$ vertices for $n\ge 5$ can be constructed from a cycle graph. The edges of a wheel graph $W_n$ can be calculated by $2(n-1)$. In this article, we are assuming graphs with more than six vertices.

Reader should know some basic definitions which will be helpful in reading this paper. A simple graph is a graph which has no loop and multiple edges [1]. A connected graph is a graph where you can move from one vertex to another by an edge [2]. If all the vertices of a graph have same degree then such a graph is called regular graph. A graph will be $t$-regular if the degree of all its vertices is $t$.

If the vertices of a graph do not have same degree then we call such graphs as irregular graphs [1]. If no two edges of a graph intersect each other then we say that graph is a planar graph [2]. Graph labelling is putting positive integers to vertices, edges and faces of the graph [3]. Weight of vertex of a graph can be calculated by adding the labels of the particular vertex and its surrounding edges, weight of an edge can be calculated by adding labels of two vertices surrounding that particular edge and the label of edge itself, weight of face can be calculated by adding the labels of surrounding vertices, edges and the label of that particular face itself. Let $\mathrm{M}$ is a mapping from the graph elements $(V,E,F)$ into the set of positive integers $\{1,2,3,\dots ,\mathbb{k}\}$ and consider the parameters $\lambda ,\mu ,\nu$ which are either zero or one. A regular relation to calculate the face weight of any plane graph $G(V,E,F)$ can be written as $W{t}_{{\mathrm{M}}_{(\lambda ,\mu ,\nu )}}(f)=\lambda \sum _{v\sim f}\mathrm{M}(v)+\mu \sum _{e\sim f}\mathrm{M}(e)+\nu \mathrm{M}(f)$ where $Wt$ stands for weight and $f$ stands for face of the graph. Suppose that $\mathbb{k}$ is a positive integer then $\mathbb{k}-$labelling of graphs is a mapping $\mathrm{M}$ from the graph elements into the set of positive integers. A $\mathbb{k}-$labelling $\mathrm{M}$ of kind $(\lambda ,\mu ,\nu )$ is defined as the face irregular $\mathbb{k}-$labelling of kind $(\lambda ,\mu ,\nu )$ if for every two faces $f_1$ and $f_2$ of the plane graph, their weights are distinct, that is, $W{t}_{{\mathrm{M}}_{(\lambda ,\mu ,\nu )}}(f_1)\ne W{t}_{{\mathrm{M}}_{(\lambda ,\mu ,\nu )}}(f_2)$. The number $\mathbb{k}$ should be the least positive integer among the set of integers and it should be the highest integer among the labelled integers in a plane graph.

The whole discussion will round over the domains $(1/0,1/0,1/0)$ where $(0,0,0)$ never exists. The $\mathbb{k}-$labelling will have different names which depend on domains. If the domain of labeling is the vertex set then we say it vertex $\mathbb{k}-$labelling of kind $(1,0,0)$, if the domain of labelling is edge set then we say it edge $\mathbb{k}-$labelling of kind $(0,1,0)$, if the domain of labelling is face set then we say it face $\mathbb{k}-$labelling of kind $(0,0,1)$, if the domain of labelling is vertex-edge set then we say it total $\mathbb{k}-$labelling of kind $(1,1,0)$, if the domain of labelling is edge-face set then we say it edge-face $\mathbb{k}-$labelling of kind $(0,1,1)$, if the domain of labelling is vertex-edge-face set then we say it entire $\mathbb{k}-$labelling of kind $(1,1,1)$. More details on $\mathbb{k}-$labelling and weights of graphs can be seen in [4, 5, 6, 7, 8].

The vertex set and edge set for wheel graphs can be written as $$\begin{array}{rl}V(W_n)& =\{v_i;i=1,2,3,\dots ,n\}.\\ E(W_n)& =\{v_1{v}_i;i=2,3,\dots ,n\}\cup \{v_i{v}_{i+1};i=2,3,\dots ,n-1\}\cup \{v_n{v}_2\}.\end{array}$$

2. Notations and Preliminary Results

Graph theory is applicable on every field around us. Authors in this study are applying the subtopic of graph theory, that is, face irregularity strength, on some particular fields where one component may be attached with other components surrounding it. The Figure 1 represents a general diagram which can be fixed to any application of face irregularity strength. Mathematically, it represents a wheel graph with twenty-one vertices, forty edges and twenty-one faces including the external face. The labeling used in this diagram is $\mathbb{k}-$labelling $\mathrm{M}$ of kind $(1,1,1)$ which is a labelling from the graph vertices, edges and faces into the set of positive integers. The numbers inside the faces, which are visible in circles, are the distinct weights of the faces. The parameters $\{c_1,c_2,\dots \}$ are the vertices in the graph, where the letter $c$ stands for component. This component will vary from field to field. If we are applying this theory on computer networking system then components will be computers, if we are applying this theory on Facebook then components will be people and vice versa. Generally, for a wheel graph under entire $\mathbb{k}-$labelling $\mathrm{M}$ of kind $(1,1,1)$, the labelling of vertices can be generalized as $\mathrm{M}(c_i)=1\text{for}i=1$; $\mathrm{M}(c_i)=\lceil \frac{i-1}{2}\rceil \text{for}i=2,3,4,\dots ,n-1$; $\mathrm{M}(c_i)=n-2\text{for}i=n$, the labelling of edges can be generalized as $\mathrm{M}\left(c_1{c}_i\right)=1\text{for}i=2,3,4,\dots ,n$; $\mathrm{M}\left(c_i{c}_{i+1}\right)=1\text{for}i=2,3,4,\dots ,n-1$; $\mathrm{M}\left(c_i{c}_2\right)=1\text{for}i=n$ and the labelling of faces can be generalized as $\mathrm{M}\left(f_i\right)=1\text{for}i=1,2,3,4,\dots ,n-1$ where $W{t}_{\mathrm{M}(1,1,1)}\left(f_{External}\right)>6n$. The integers besides the vertices are the labels of vertices which are arranged in a sequence so that reader can easily understand them. The generalized formula is also elaborated so that you can construct any graph yourself. The labels of edges and faces are designed in the most easiest format, that is one for every edge and face. The weighs of faces are calculated by adding the labels of vertices, edges and the included face itself. For example, the weight of face 1 is equal to $1+1+1+1+1+1+1=7$ and so on. The label of any edge, one, shows that there is one characteristic, behavior or trait between the two components. This label, one, can be designed in any format which depends on the category and its situation. In case of large numbers, they can be scaled down or can be compressed into smaller integers to maintain the existence of least positive integer $\mathbb{k}$. Similar procedure can be analyzed with vertices and faces.

3. Java Codes to Construct a Wheel Graph with 21 Vertices

import java.util.ArrayList;
import java.util.List;

public class WheelGraph {

    public static void main(String[] args) {
        int n = 21; // Number of vertices
        List<List<Integer>> adjList = constructWheelGraph(n);
        printGraph(adjList);
    }

    // Step 1: Function to construct a wheel graph with n vertices
    public static List<List<Integer>> constructWheelGraph(int n) {
        // Step 2: Initialize the adjacency list
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        // Step 3: Connect the outer cycle
        for (int i = 0; i < n - 1; i++) {
            adjList.get(i).add((i + 1) % (n - 1));
            adjList.get((i + 1) % (n - 1)).add(i);
        }

        // Step 4: Connect the hub vertex to all outer vertices
        for (int i = 0; i < n - 1; i++) {
            adjList.get(n - 1).add(i);
            adjList.get(i).add(n - 1);
        }

        return adjList;
    }

    // Step 5: Function to print the adjacency list representation 
    of the graph
    public static void printGraph(List<List<Integer>> adjList) {
        for (int i = 0; i < adjList.size(); i++) {
            System.out.print("Vertex " + i + " is connected to: ");
            for (int neighbor : adjList.get(i)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
}

4. Finding best Friends around you by using Face Irregularity Strength of Graphs

Chao has a friends circle. He always face deceit from his friends. He is going to use face irregularity strength of graphs to find sincere friends in his circle. Chao has seven friends who are always close to him but he is confused to choose the best of them. He does not want to face deceit again. The Figure 2 shows that chao is using a popular graph in graph theory to choose his friends. This graph is a wheel graph, which is labelled under $\mathbb{k}-$labelling of kind $(1,0,1)$ because chao likes to solve his problems by the help of graph theory. If chao uses entire $\mathbb{k}-$labelling of kind $(1,1,1)$ of graphs then the additional feature in his friends will be the edge labelling which is always one for every edge so chao did not use the feature which is same in all his friends. You can see from diagram 2 that friends of chao are Lisha, Kexin, Dandan, Lihua, Jing, Fang, Ming. Fang and Lisha always try to be close to chao to get his full attraction towards them but chao does not know what is going on in their hearts, so chao uses graph theory to analyze the traits among his friends. Chao is looking for honest person because he never wants to face deceit again in his life. But he wants to compare their traits and then he will analyze by the help of face irregularity strength of this graph. The numbers, which are given to chao friends, are their number of traits, which are as follows. $\text{Lisha}=\{\text{decent}\}$; $\text{Kexin}=\{\text{honest}\}$; $\text{Dandan}=\{\text{kind, beautiful}\}$; $\text{Lihua}=\{\text{trustworthy, goodlistener}\}$; $\text{Jing}=\{\text{kind, honest, beautiful}\}$ ; $\text{Fang}=\{\text{forgiving, kind, softhearted}\}$; $\text{Ming}=\{\text{honest, beautiful, kind, soft hearted, good listener,decent}\}$.

Chao categorizes his friends into a wheel graph with six faces and every face contains three friends. His sixth sense works well now because he has faced many frauds in his life so he uses his sixth sense and gives numbering to every face of the graph. The condition behind these numbering is that the face weights should be distinct. Moving from top to clock wise, we see that numberings given by chao to the faces are, 1, 2, 3, 4, 5, 7 and 6. The condition of this k-numbering is that the face weights should be distinct which you can clearly see from the Figure 2. The face weights are shown in the circles inside each face, which are 4, 6, 8, 10, 12, 17 and 14 if we move in clock wise direction from Lisha.

Now the decision time comes here. Chao will first check the face irregularity strength of this graph. The face irregularity strength of a graph is the minimum integer (from the set of integers) in a graph for which the face weights are distinct. We can see clearly that the face irregularity strength of the Figure 2 is 7 which falls in the face containing Fang, Ming and Chao. So now chao has to choose Fang or Ming. Chao gave them number 7 because he was already interested in both of them because of their good traits. But chao has to choose one of them so he will go for Ming because Ming has much better traits as compare to Fang. So face irregularity strength in graph theory made it easy for chao to choose a best lifetime friend. Graph theory itself plays very important character in our everyday life problems but now the subtopics of graph theory need to apply on our routine life, which authors have done in this research.

Remember that the numberings which chao used in his graph need not to be in order. You can assign integers according to your own wish but the face weight should be distinct and the least possible integers need to be used in your labelling. The numbers which are given to the edges and faces can also be others except one but you have to focus the whole graph, like, if you are giving a number 14 to the vertices then try to use a number less than 14 for the faces or edges. For larger number applications, you can use a scale to put them in a label form. For example, if you want to use the total number of engineering students of India in the graph then you can use scale, like, $1000000$ equal to label $1$ in the graph and vice versa.

5. Algorithm

1. Step 1: The vertices $c_i$ for $1\le i\le n$ represent the components.

2. Step 2: One component will totally be operated as a full house, full country, full computer, full body etc. The numbers in decimals should be avoided.

3. Step 3: Label vertices, edges and faces with $\mathbb{k}-$labeling where $\mathbb{k}$ is the least positive integer.

4. Step 4: Calculate weights by using $W{t}_{\mathrm{M}(\lambda ,\mu ,\nu )}(f)=\lambda \sum _{v\sim f}\mathrm{M}(v)+\mu \sum _{e\sim f}\mathrm{M}(e)+\nu \mathrm{M}(f)$ where $\lambda$, $\mu$ and $\nu$ are associated with vertices, edges and faces.

5. Step 5: Analyze the face containing irregularity strength of the graph.

6. Step 6: When labelling a graph then keep a good care of distinct face weights otherwise operation will not be successful.

7. Step 7: This theory will work much better on the structure where one thing will be attached with some other things in the surrounding.

6. Conclusion

Authors in this study made a user friendly system for the solution of our everyday routine life problems. They highlighted the environment for vertex, edge, face, total, edge-face, vertex-face and entire. This shows that almost every problem of everyday life can be dissolved according to this model. Writers applied this study on a local school which was successful in making cost effective transport system. In future, there is still much more space where applications of graph theory can be fixed.