Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Theory of Colorful Graphs
202
0
0.0
(
0
)
Authors
Dhananjay P. Mehendale
Ask ChatGPT about the research
No Arabic abstract
The theory of colorful graphs can be developed by working in Galois field modulo (p), p > 2 and a prime number. The paper proposes a program of possible conversion of graph theory into a pleasant colorful appearance. We propose to paint the usual black (indicating presence of an edge) and white (indicating absence of an edge) edges of graphs using multitude of colors and study their properties. All colorful graphs considered here are simple, i.e. not having any multiple edges or self-loops. This paper is an invitation to the program of generalizing usual graph theory in this direction.
rate research
Read More
Given an $n$ vertex graph whose edges have colored from one of $r$ colors $C={c_1,c_2,ldots,c_r}$, we define the Hamilton cycle color profile $hcp(G)$ to be the set of vectors $(m_1,m_2,ldots,m_r)in [0,n]^r$ such that there exists a Hamilton cycle that is the concatenation of $r$ paths $P_1,P_2,ldots,P_r$, where $P_i$ contains $m_i$ edges. We study $hcp(G_{n,p})$ when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when $hcp(G_{n,p})={(m_1,m_2,ldots,m_r)in [0,n]^r:m_1+m_2+cdots+m_r=n}$.
The problem of finding paths in temporal graphs has been recently considered due to its many applications. In this paper we consider a variant of the problem that, given a vertex-colored temporal graph, asks for a path whose vertices have distinct colors and include the maximum number of colors. We study the approximation complexity of the problem and we provide an inapproximability lower bound. Then we present a heuristic for the problem and an experimental evaluation of our heuristic, both on synthetic and real-world graphs.
Let $P(G,lambda)$ denote the number of proper vertex colorings of $G$ with $lambda$ colors. The chromatic polynomial $P(C_n,lambda)$ for the cycle graph $C_n$ is well-known as $$P(C_n,lambda) = (lambda-1)^n+(-1)^n(lambda-1)$$ for all positive integers $nge 1$. Also its inductive proof is widely well-known by the emph{deletion-contraction recurrence}. In this paper, we give this inductive proof again and three other proofs of this formula of the chromatic polynomial for the cycle graph $C_n$.
The concept of graceful labels was proposed by Rosa, scholars began to study graceful labels of various graphs and obtained relevant results.Let the graph is a bipartite graceful graph, we have proved some graphs are graceful labeling in this paper.
A new characterisation of Hamiltonian graphs using f-cutset matrix is proposed. A new exact polynomial time algorithm for the travelling salesman problem (TSP) based on this new characterisation is developed. We then define so called ordered weighted adjacency list for given weighted complete graph and proceed to the main result of the paper, namely, the exact algorithm based on utilisation of ordered weighted adjacency list and the simple properties that any path or circuit must satisfy. This algorithm performs checking of sub-lists, containing (p-1) entries (edge pairs) for paths and p entries (edge pairs) for circuits, chosen from ordered adjacency list in a well defined sequence to determine exactly the shortest Hamiltonian path and shortest Hamiltonian circuit in a weighted complete graph of p vertices. The procedure has intrinsic advantage of landing on the desired solution in quickest possible time and even in worst case in polynomial time. A new characterisation of shortest Hamiltonian tour for a weighted complete graph satisfying triangle inequality (i.e. for tours passing through every city on a realistic map of cities where cities can be taken as points on a Euclidean plane) is also proposed. Finally, we propose a classical algorithm for unstructured search and also three new quantum algorithms for unstructured search which exponentially speed up the searching ability in the unstructured database and discuss its effect on the NP-Complete problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
