Narayanan N

The exact distance p-power of a graph G, denoted G[#p], is a graph on vertex set V(G) in which two vertices are adjacent if they are at distance exactly p in G. Given integers k and p, we define f(k, p) to be the maximum possible order of a clique in the exact distance p-powers of graphs with maximum degree k + 1. It is easily observed that f(k, 2) ≤ k2+ k + 1. We prove that equality may only hold if a connected component of G is isomorphic to a member of the class Pk of incidence graphs of finite projective k-geometries. (These famous combinatorial structures are known to exist when k is a prime power, and are conjectured not to exist for other values of k.) We then study the case of graphs of maximum degree k + 1 with clique number k2+ k. One way to obtain such a graph is to remove a vertex from a graph in P k; we call Pk' the class of all such resulting graphs. We prove that for any graph G of maximum degree k + 1 whose exact square has a (k2+ k)-clique, either G has a subgraph isomorphic to a graph in P'k, or a connected component of G is a (k + 1)-regular bipartite graph of order 2(k2+ k). We call Okthe class of such bipartite graphs, and study their structural properties. These properties imply that (if they exist) the graphs in Okmust be highly symmetric. Using this structural information, we show that O2contains only one graph, known as the Franklin graph. We then show that O3also consists of a single graph, which we build. Furthermore, we show that O4and O5are empty. For general values of p, we prove that f(k, p) ≤ (k + 1)k[p/2]+ 1, and that the bound is tight for every odd integer p ≥ 3. This implies that f(k, 2) = f(k, 3) whenever there exists a finite projective k-geometry, however, in such a case, the bound of f(k, 3) could also be reached by highly symmetric graphs built from a finite k-geometry, which is not the case for other values of k.

In this paper we study a generalization of both proper edge-coloring and strong edge-coloring: k-intersection edge-coloring, introduced by Muthu, Narayanan and Subramanian. In this coloring, the set S(v) of colors used by edges incident to a vertex v does not intersect S(u) on more than k colors when u and v are adjacent. We provide some sharp upper and lower bounds for χ′k-int for several classes of graphs. For l-degenerate graphs we prove that χ′k-int(G)≤(l+1)Δ−l(k−1)−1. We improve this bound for subcubic graphs by showing that χ′2-int(G)≤6. We show that calculating χ′k-int(Kn) for arbitrary values of k and n is related to some problems in combinatorial set theory and we provide bounds that are tight for infinitely many values of n. Furthermore, for complete bipartite graphs we prove that χ′k-int(Kn, m)=⌈mn/k⌉. Finally, we show that computing χ′k-int(G) is NP-complete for every k≥1.

The axiomatic study on the interval function, induced pathfunction of a connected graph is a well-known area in metric graph theory. In this paper, we present a new axiom: (bp)for anyx,y,z∈V,R(x,y)={x,y}⇒y∈R(x,z)orx∈R(y,z).We study axiom (bp) on the interval function and the induced path function of a connected, simple and finite graph. We present axiomatic characterizations of the interval function of bipartite graphs and complete bipartite graphs. We extend the characterization of the interval function of bipartite graphs to arbitrary bipartite graphs including disconnected bipartite graphs. In addition, we present an axiomatic characterization of the interval function of a forest. Finally, we present an axiomatic characterization of the induced path function of a tree or a 4-cycle using the axiom (bp).

In this paper, we have obtained upper bounds for the total chromatic number of some classes of Cayley graphs, odd graphs and mock threshold graphs.

The axiomatic study on the interval function, induced path function and all-paths function of a connected graph is a well-known area in metric graph theory and related areas. In this paper, we introduce the following new axiom: (cp) v∈R(u,w) and v∈R(u,x)⇒w∈R(v,x) or x∈R(v,w), for all distinct u,v,w,x∈V.We present characterizations of (claw, paw)-free graphs using axiom (cp) on the standard path transit functions on graphs, namely the interval function, the induced path function, and the all-paths function. We study the underlying graphs of the transit functions which are (claw, paw)-free and Hamiltonian. We present an axiomatic characterization of the interval function on (claw, paw)-free graphs. Furthermore, we obtain an axiomatic characterization of the induced path function on a subclass of (claw, paw)-free graphs.

The axiomatic approach with the interval function and induced path transit function of a connected graph is an interesting topic in metric and related graph theory. In this paper, we introduce a new axiom: (bp) for any x, y, z ∈ V, R(x, y) = {x, y} ⇒ y ∈ R(x, z) or x ∈ R(y, z). We study axiom (bp) on the interval function and the induced path transit function of a connected, simple and finite graph. We present axiomatic characterizations of the interval function of bipartite graphs and complete bipartite graphs. Further, we present an axiomatic characterization of the induced path transit function of a tree or a 4-cycle.

If in a directed graph, v is an out-neighbor of u and w is an out-neighbor of v but not of u, then w is said to be a second out-neighbor of u. A vertex in a directed graph is said to have a large second neighborhood if it has at least as many second out-neighbors as out-neighbors. The Second Neighborhood Conjecture, first stated by Seymour, asserts that there is a vertex having a large second neighborhood in every oriented graph (a directed graph without loops or digons). It is straightforward to see that the conjecture is true for any oriented graph whose underlying undirected graph is bipartite. We extend this to show that the conjecture holds for oriented graphs whose vertex set can be partitioned into an independent set and a 2-degenerate graph. Fisher proved the conjecture for tournaments and later Havet and Thomassé provided a different proof for the same using median orders of tournaments. Havet and Thomassé in fact showed the stronger statement that if a tournament contains no sink, then it contains at least two vertices with large second neighborhoods. Using their techniques, Fidler and Yuster showed that the conjecture remains true for tournaments from which either a matching or a star has been removed. We extend this result to show that the conjecture holds even for tournaments from which both a matching and a star have been removed. This implies that a tournament from which a matching has been removed contains either a sink or two vertices with large second neighborhoods.

In this note we extend the Mulder-Nebeský characterization of the interval function of a connected graph to the disconnected case. One axiom needs to be adapted, but also a new axiom is needed in addition.

The smallest integer k needed for the assignment of k colors to the elements so that the coloring is proper (vertices and edges) is called the total chromatic number of a graph. Vizing [126] and Behzad [6, 7] conjectured that the total coloring can be done using at most (Formula presented.) colors, where (Formula presented.) is the maximum degree of G. It is not settled even for planar graphs. In this paper, we give a survey on the total coloring of graphs.

A strong edge coloring of a graph G is a proper edge coloring of G such that every color class is an induced matching. The minimum number of colors required is termed the strong chromatic index. In this paper we determine the exact value of the strong chromatic index of all unitary Cayley graphs. Our investigations reveal an underlying product structure from which the unitary Cayley graphs emerge. We then go on to give tight bounds for the strong chromatic index of the Cartesian product of two trees, including an exact formula for the product in the case of stars. Further, we give bounds for the strong chromatic index of the product of a tree with a cycle. For any tree, those bounds may differ from the actual value only by not more than a small additive constant (at most 2 for even cycles and at most 4 for odd cycles), moreover they yield the exact value when the length of the cycle is divisible by 4.