Clique Irreducibility and Clique Vertex Irreducibility of Graphs

A graphs G is clique irreducible if every clique in G of size at least two,has an edge which does not lie in any other clique of G and is clique reducible if it is not clique irreducible. A graph G is clique vertex irreducible if every clique in G has a vertex which does not lie in any other clique of G and clique vertex reducible if it is not clique vertex irreducible. The clique vertex irreducibility and clique irreducibility of graphs which are non-complete extended p-sums (NEPS) of two graphs are studied. We prove that if G(c) has at least two non-trivial components then G is clique vertex reducible and if it has at least three non-trivial components then G is clique reducible. The cographs and the distance hereditary graphs which are clique vertex irreducible and clique irreducible are also recursively characterized.

Strongly distance-balanced graphs and graph products

A graph G is strongly distance-balanced if for every edge uv of G and every i 0 the number of vertices x with d.x; u/ D d.x; v/ 1 D i equals the number of vertices y with d.y; v/ D d.y; u/ 1 D i. It is proved that the strong product of graphs is strongly distance-balanced if and only if both factors are strongly distance-balanced. It is also proved that connected components of the direct product of two bipartite graphs are strongly distancebalanced if and only if both factors are strongly distance-balanced. Additionally, a new characterization of distance-balanced graphs and an algorithm of time complexity O.mn/ for their recognition, wheremis the number of edges and n the number of vertices of the graph in question, are given

Equal opportunity networks, distance-balanced graphs, and Wiener game

Given a graph G and a set X ⊆ V(G), the relative Wiener index of X in G is defined as WX (G) = {u,v}∈X 2  dG(u, v) . The graphs G (of even order) in which for every partition V(G) = V1 +V2 of the vertex set V(G) such that |V1| = |V2| we haveWV1 (G) = WV2 (G) are called equal opportunity graphs. In this note we prove that a graph G of even order is an equal opportunity graph if and only if it is a distance-balanced graph. The latter graphs are known by several characteristic properties, for instance, they are precisely the graphs G in which all vertices u ∈ V(G) have the same total distance DG(u) = v∈V(G) dG(u, v). Some related problems are posed along the way, and the so-called Wiener game is introduced.

On Distance Energy of Graphs

The D-eigenvalues of a graph G are the eigenvalues of its distance matrix D, and the D-energy ED(G) is the sum of the absolute values of its D-eigenvalues. Two graphs are said to be D-equienergetic if they have the same D-energy. In this note we obtain bounds for the distance spectral radius and D-energy of graphs of diameter 2. Pairs of equiregular D-equienergetic graphs of diameter 2, on p = 3t + 1 vertices are also constructed.

ON DISTANCE ENERGY OF GRAPHS

The D-eigenvalues of a graph G are the eigenvalues of its distance matrix D, and the D-energy ED(G) is the sum of the absolute values of its D-eigenvalues. Two graphs are said to be D-equienergetic if they have the same D-energy. In this note we obtain bounds for the distance spectral radius and D-energy of graphs of diameter 2. Pairs of equiregular D-equienergetic graphs of diameter 2, on p = 3t + 1 vertices are also constructed.

Simultaneous Embeddings Of Graphs As Median And Antimedian Subgraphs

The distance DG(v) of a vertex v in an undirected graph G is the sum of the distances between v and all other vertices of G. The set of vertices in G with maximum (minimum) distance is the antimedian (median) set of a graph G. It is proved that for arbitrary graphs G and J and a positive integer r 2, there exists a connected graph H such that G is the antimedian and J the median subgraphs of H, respectively, and that dH(G, J) = r. When both G and J are connected, G and J can in addition be made convex subgraphs of H.

The Plurality Strategy on Graphs

The Majority Strategy for finding medians of a set of clients on a graph can be relaxed in the following way: if we are at v, then we move to a neighbor w if there are at least as many clients closer to w than to v (thus ignoring the clients at equal distance from v and w). The graphs on which this Plurality Strategy always finds the set of all medians are precisely those for which the set of medians induces always a connected subgraph

Consensus strategies for signed profiles on graphs

The median problem is a classical problem in Location Theory: one searches for a location that minimizes the average distance to the sites of the clients. This is for desired facilities as a distribution center for a set of warehouses. More recently, for obnoxious facilities, the antimedian was studied. Here one maximizes the average distance to the clients. In this paper the mixed case is studied. Clients are represented by a profile, which is a sequence of vertices with repetitions allowed. In a signed profile each element is provided with a sign from f+; g. Thus one can take into account whether the client prefers the facility (with a + sign) or rejects it (with a sign). The graphs for which all median sets, or all antimedian sets, are connected are characterized. Various consensus strategies for signed profiles are studied, amongst which Majority, Plurality and Scarcity. Hypercubes are the only graphs on which Majority produces the median set for all signed profiles. Finally, the antimedian sets are found by the Scarcity Strategy on e.g. Hamming graphs, Johnson graphs and halfcubes

Studies on Fuzzy Graphs

In this thesis an attempt to develop the properties of basic concepts in fuzzy graphs such as fuzzy bridges, fuzzy cutnodes, fuzzy trees and blocks in fuzzy graphs have been made. The notion of complement of a fuzzy graph is modified and some of its properties are studied. Since the notion of complement has just been initiated, several properties of G and G available for crisp graphs can be studied for fuzzy graphs also. Mainly focused on fuzzy trees defined by Rosenfeld in [10] , several other types of fuzzy trees are defined depending on the acyclicity level of a fuzzy graph. It is observed that there are selfcentered fuzzy trees. Some operations on fuzzy graphs and prove that complement of the union two fuzzy graphs is the join of their complements and complement of the join of two fuzzy graphs is union of their complements. The study of fuzzy graphs made in this thesis is far from being complete. The wide ranging applications of graph theory and the interdisciplinary nature of fuzzy set theory, if properly blended together could pave a way for a substantial growth of fuzzy graph theory.

Clique Irreducibility of Some Iterative Classes of Graphs

In this paper, two notions, the clique irreducibility and clique vertex irreducibility are discussed. A graph G is clique irreducible if every clique in G of size at least two, has an edge which does not lie in any other clique of G and it is clique vertex irreducible if every clique in G has a vertex which does not lie in any other clique of G. It is proved that L(G) is clique irreducible if and only if every triangle in G has a vertex of degree two. The conditions for the iterations of line graph, the Gallai graphs, the anti-Gallai graphs and its iterations to be clique irreducible and clique vertex irreducible are also obtained.

A Note on Energy of Some Graphs

Eigenvalue of a graph is the eigenvalue of its adjacency matrix. The energy of a graph is the sum of the absolute values of its eigenvalues. In this note we obtain analytic expressions for the energy of two classes of regular graphs.

Equienergetic self-complementary graphs

In this paper equienergetic self-complementary graphs on p vertices for every p = 4k; k ¸ 2 and p = 24t + 1; t ¸ 3 are constructed

Some classes of Turker equivalent graphs

Two graphs G and H are Turker equivalent if they have the same set of Turker angles. In this paper some Turker equivalent family of graphs are obtained.

The (t) property of some classes of graphs

In this note,the (t) properties of five class are studied. We proved that the classes of cographs and clique perfect graphs without isolated vertices satisfy the (2) property and the (3) property, but do not satisfy the (t) property for tis greater than equal to 4. The (t) properties of the planar graphs and the perfect graphss are also studied . we obtain a necessary and suffieient conditions for the trestled graph of index K to satisfy the (2) property

SOME NEW INTEGRAL GRAPHS

The eigenvalue of a graph is the eigenvalue of its adjacency matrix . A graph G is integral if all of its cigenvalues are integers. In this paper some new classes of integral graphs are constructed.