On a novel eccentricity-based invariant of a graph

In this paper,for the purpose of measuring the non-self-centrality extent of non-selfcentered graphs,a novel eccentricity-based invariant,named as non-self-centrality number(NSC number for short),of a graph G is defined as follows:N(G)=∑v_i,v_j∈V(G)|e_i-e_j| where the summation goes over all the unordered pairs of vertices in G and e_i is the eccentricity of vertex v_i in G,whereas the invariant will be called third Zagreb eccentricity index if the summation only goes over the adjacent vertex pairs of graph G.In this paper,we determine the lower and upper bounds on N(G) and characterize the corresponding graphs at which the lower and upper bounds are attained.Finally we propose some attractive research topics for this new invariant of graphs.     

On a graph associated to invariant conjugacy classes of finite groups

LetA andG be finite groups of coprime orders such thatA acts by automorphisms onG. We define theA-invariant conjugacy class graph ofG to be the graph having as vertices the noncentralA-invariant conjugacy classes ofG, and two vertices are connected by an edge if their cardinalities are not coprime. We prove that when the graph is disconnected thenG is solvable.     

Convex graph invariant relaxations for graph edit distance

Mathematical Programming - The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to...     

On the optimality of the Arf invariant formula for graph polynomials

We prove optimality of the Arf invariant formula for the generating function of even subgraphs, or, equivalently, the Ising partition function, of a graph.     

An invariant theory approach to graph enumeration

The paper exploits a connection between the graphs on n vertices and the invariants of the pair group S⁽²⁾_n.     

On the hamiltonian path graph of a graph

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and v are adjacent if and only if F contains a hamiltonian u ? v path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian graphs isomorphic to their hamiltonian path graphs is presented. Next, the maximum size of a hamiltonian graph F of given order such that K?_d ? H(F) is determined. Finally, it is shown that if the degree sum of the endvertices of a hamiltonian path in a graph F with at least five vertices is at least |V(F)| + t(t ? 0), then H(F) contains a complete subgraph of order t + 4.     

On thel-connectivity of a graph

For an integerl 2, thel-connectivity of a graphG is the minimum number of vertices whose removal fromG produces a disconnected graph with at leastl components or a graph with fewer thanl vertices. A graphG is (n, l)-connected if itsl-connectivity is at leastn. Several sufficient conditions for a graph to be (n, l)-connected are established. IfS is a set ofl( 3) vertices of a graphG, then anS-path ofG is a path between distinct vertices ofS that contains no other vertices ofS. TwoS-paths are said to be internally disjoint if they have no vertices in common, except possibly end-vertices. For a given setS ofl 2 vertices of a graphG, a sufficient condition forG to contain at leastn internally disjointS-paths, each of length at most 2, is established.     

On a graph of ideals

We associate a graph Γ₊(R) to a ring R whose vertices are nonzero proper right ideals of R and two vertices I and J are adjacent if I+J=R. Then we try to translate properties of this graph into algebraic properties of R and vice versa. For example, we characterize rings R for which Γ₊(R) respectively is connected, complete, planar, complemented or a forest. Also we find the dominating number of Γ₊(R).     

On graphs whose Laplacian matrix’s multipartite separability is invariant under graph isomorphism

Normalized Laplacian matrices of graphs have recently been studied in the context of quantum mechanics as density matrices of quantum systems. Of particular interest is the relationship between quantum physical properties of the density matrix and the graph theoretical properties of the underlying graph. One important aspect of density matrices is their entanglement properties, which are responsible for many nonintuitive physical phenomena. The entanglement property of normalized Laplacian matrices is in general not invariant under graph isomorphism. In recent papers, graphs were identified whose entanglement and separability properties are invariant under isomorphism. The purpose of this note is to completely characterize the set of graphs whose separability is invariant under graph isomorphism. In particular, we show that this set consists of K_2,2 and its complement, all complete graphs and no other graphs.     

On the eulericity of a graph

The eulericity ?(G) of a bridgeless graph G is defined as the least number of eulerian subgraphs of G which together cover the lines of G. A 1–1 correspondence is shown to exist between the k-tuples of eulerian subgraphs of G and the proper flows (mod2^k) on a given network based on G. The inequality ?(G) ? 3 them follows from a result of Jaeger.     

On the chordality of a graph

The chordality of a graph G = (V, E) is defined as the minimum k such that we can write E = E₁ ∩ … ∩ E_k with each (V, E_i) a chordal graph. We present several results bounding the value of this generalization of boxicity. Our principal result is that the chordality of a graph is at most its tree width. In particular, series-parallel graphs have chordality at most 2. Potential strengthenings of this statement fail in that there are planar graphs with chordality 3 and series-parallel graphs with boxicity 3. © 1993 John Wiley & Sons, Inc.     

On the residue of a graph

The residue R of a simple graph G of degree sequence S: d₁ ? d₂ ? …? ? d_n is the number of zeros obtained by the iterative process consisting of deleting the first term d₁ of S, subtracting 1 from the d₁ following ones, and sorting down the new sequence. The depth is the number n - R of steps in this algorithm. We prove here some conjectures given by the computer program GRAFFITI, in particular, .     

On incidence energy of a graph

The Laplacian-energy like invariant LEL(G) and the incidence energy IE(G) of a graph are recently proposed quantities, equal, respectively, to the sum of the square roots of the Laplacian eigenvalues, and the sum of the singular values of the incidence matrix of the graph G. However, IE(G) is closely related with the eigenvalues of the Laplacian and signless Laplacian matrices of G. For bipartite graphs, IE=LEL. We now point out some further relations for IE and LEL: IE can be expressed in terms of eigenvalues of the line graph, whereas LEL in terms of singular values of the incidence matrix of a directed graph. Several lower and upper bounds for IE are obtained, including those that pertain to the line graph of G. In addition, Nordhaus-Gaddum-type results for IE are established.     

On a simple invariant of Turaev-Viro type

For 3-manifolds, we define an invariant t(M)=a+bε, where a,b are integers and . An advantage of the invariant is that it admits a very simple interpretation in terms of a fake surface and a simple geometric proof of the invariance. Actually, it coincides with the homologically trivial part of the Turaev-Viro invariant of degree r=5. Extensive tables for all closed irreducible orientable 3-manifolds of complexity less than or equal to six are explicitly presented. Similar tables for r=3,4 were composed by L. H. Kauffman and S. Lins. Bibliography: 8 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 234, 1996, pp. 137–142.     

On the dimension to represent a graph by a unit distance graph

It is proved that if a graphG has maximum degreed, then its vertices can be represented by distinct unit vectors inR ^2d so that two vectors are orthogonal if and only if the corresponding vertices are adjacent. As a corollary it follows that if a graph has maximum degreed, then it is isomorphic to a unit distance graph inR ^2d.     

On the graph for which there is a tree as the inverse interchange graph of a local graph

Let G be a finite, connected, undirected graph without loops and multiple edges. The note modifies slightly the concept of I^–1 (T_t), the inverse interchange graph of the local graph G(T_t) defined by a reference tree t G, and considers the properties of the graph G, when I^–1(T_t) is a tree.     

On the degree distance of a graph

If G is a connected graph with vertex set V, then the degree distance of G, D^′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].