The imbedding index of a graph

The natural extension of MacLane's combinatorial approach to planar imbeddings is seen to yield a combinatorial formulation of imbedding of a graph in a pseudosurface. This leads to a combinatorially defined parameter for all graphs, called the imbedding index. A generalization of the Heaword inequality is then proved for this parameter.     

The edge-Wiener index of a graph

If G is a connected graph, then the distance between two edges is, by definition, the distance between the corresponding vertices of the line graph of G. The edge-Wiener index W_e of G is then equal to the sum of distances between all pairs of edges of G. We give bounds on W_e in terms of order and size. In particular we prove the asymptotically sharp upper bound for graphs of order n.     

The skew chromatic index of a graph

We define a skew edge coloring of a graph to be a set of two edge colorings such that no two edges are assigned the same unordered pair of colors. The skew chromatic index s(G) is the minimum number of colors required for a skew edge coloring of G. We show that this concept is closely related to that of skew Room squares and use this relation to prove that s(G) is at most o(G) + 4. We also find better upper bounds for s(G) when G is cyclic, cubic, or bipartite. In particular we use a construction involving Latin squares to show that if G is complete bipartite of order 2n, s(G) is bounded above by roughly $\text{3n}\text{2}$.     

The hamiltonian index of a 2-connected graph

Let G be a graph. Then the hamiltonian index h(G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l≥3. We also show that for any two 2-connected nonhamiltonian graphs G and with at least 74 vertices. The upper bounds are all sharp.     

Separation index of a graph

The concepts of separation index of a graph and of a surface are introduced. We prove that the separation index of the sphere is 3. Also the separation index of any graph faithfully embedded in a surface of genus g is bounded by a funtion of g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 53–61, 2002     

Sum-connectivity index of a graph

Let G be a simple connected graph, and let di be the degree of its i-th vertex. The sum-connectivity index of the graph G is defined as χ(G)=Σvivj∈E(G)? (di+dj)−1/2. We discuss the effect on χ(G) of inserting an edge into a graph. Moreover, we obtain the relations between sum-connectivity index and Randić index.     

Generalized outerplanar index of a graph

We define the generalized outerplanar index of a graph and give a full characterization of graphs with respect to this index.     

Critically cochromatic graphs

A graph G is critically n-cochromatic if (its cochromatic number) z(G) = n and z(G - v) = n - 1 for every vertex v of G. Properties of critically n-cochromatic graphs are discussed and we also construct graphs that are critically n-chromatic and critically n-cochromatic.     

Some topics in cochromatic theory

GivenG, a graph, the cochromatic number,Z(G), ofG is the fewest number of sets into which the vertex set can be partitioned so that each set induces a complete or an empty graph. A graph is critically cochromatic if the removal of any of its vertices decreases its cochromatic number. A graph is uniquely cochromatic if there is exactly one partition of minimum order in which each set induces a complete or an empty graph. A graph is comaximal if the removal of any edge increases its cochromatic number. These and related concepts are examined.     

The hyper-Zagreb index and some graph operations

Let G be a simple connected graph. The Hyper-Zagreb index is defined as \(\textit{HM}(G)=\sum _{uv\in E_{G}}(d_{G}(u)+d_{G}(v))^2\). In this paper some exact expressions for the hyper-Zagreb index of graph operations containing cartesian product and join of n graphs, splice, link and chain of graphs will be presented. We also apply these results to some graphs to chemical and general interest, such as \(C_4\) nanotube, rectangular grid, prism, complete n-partite graph.     

On the eccentric connectivity index of a graph

If G is a connected graph with vertex set V, then the eccentric connectivity index of G, ξ^C(G), is defined as where is the degree of a vertex v and is its eccentricity. We obtain an exact lower bound on ξ^C(G) in terms of order, and show that this bound is sharp. An asymptotically sharp upper bound is also derived. In addition, for trees of given order, when the diameter is also prescribed, precise upper and lower bounds are provided.     

On the 2-factor index of a graph

The 2-factor index of a graph G, denoted by f(G), is the smallest integer m such that the m-iterated line graph L^m(G) of G contains a 2-factor. In this paper, we provide a formula for f(G), and point out that there is a polynomial time algorithm to determine f(G).     

Finite index subgroups of graph products

We prove that every quasiconvex subgroup of a right-angled Coxeter group is an intersection of finite index subgroups. From this we deduce similar separability results for other types of groups, including graph products of finite groups and right-angled Artin groups.      

Bounds on the index of the signless Laplacian of a graph

Let G=(V,E) be a simple, undirected graph of order n and size m with vertex set V, edge set E, adjacency matrix A and vertex degrees Δ=d₁≥d₂≥?≥d_n=δ. The average degree of the neighbor of vertex v_i is . Let D be the diagonal matrix of degrees of G. Then L(G)=D(G)−A(G) is the Laplacian matrix of G and Q(G)=D(G)+A(G) the signless Laplacian matrix of G. Let μ₁(G) denote the index of L(G) and q₁(G) the index of Q(G). We survey upper bounds on μ₁(G) and q₁(G) given in terms of the d_i and m_i, as well as the numbers of common neighbors of pairs of vertices. It is well known that μ₁(G)≤q₁(G). We show that many but not all upper bounds on μ₁(G) are still valid for q₁(G).     

On the fractional chromatic index of a graph and its complement

Jensen and Toft conjectured that for a graph with an even number of vertices, either the minimum number of colours in a proper edge colouring is equal to the maximum vertex degree, or this is true in its complement. We prove a fractional version of this conjecture.