Equitable coloring on total graph of bigraphs and central graph of cycles and paths.
For a vertex in a graph , the set consists of those vertices of whose distance from is 2. If a graph contains a set of vertices such that the sets , , form a partition of , then is called a -step domination graph. We describe -step domination graphs possessing some prescribed property. In addition, all -step domination paths and cycles are determined.
Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖u)|+d(u) ≥ n-1. Using the concept of dual closure, we prove that 1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇ 2. G is nonhamiltonian if and only if its 0-dual closure is either the graph , 1 ≤ r ≤ s ≤ t or the graph . It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity of a graph...
For a nontrivial connected graph , the -degree of a vertex in a graph is the number of copies of in containing . A graph is -continuous (or -degree continuous) if the -degrees of every two adjacent vertices of differ by at most 1. All -continuous graphs are determined. It is observed that if is a nontrivial connected graph that is -continuous for all nontrivial connected graphs , then either is regular or is a path. In the case of a 2-connected graph , however, there...
We investigate the properties of the least-squares solution of the system of equations with a matrix being the incidence matrix of a given undirected connected graph and we propose an algorithm that uses this solution for finding a vertex-disjoint cycle cover (2-factor) of the graph .
We introduce the notion of fundamental groupoid of a digraph and prove its basic properties. In particular, we obtain a product theorem and an analogue of the Van Kampen theorem. Considering the category of (undirected) graphs as the full subcategory of digraphs, we transfer the results to the category of graphs. As a corollary we obtain the corresponding results for the fundamental groups of digraphs and graphs. We give an application to graph coloring.