Independence and graph homomorphisms graph homomorphisms

A graph with n vertices that contains no triangle and no 5-cycle and minimum degree exceeding n/4 contains an independent set with at least (3n)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7-cycle and invoking the No Homomorphism Lemma. For k ≥ 4, a graph with n vertices, odd girth 2k+1, and minimum degree exceeding n/(k+1) contains an independent set with at least kn/(2k+1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.     

Every connected graph is a query graph

Let V be a set of bit strings of length k, i.e., V ? {0, 1}^k. The query graph Q(V) is defined as follows: the vertices of Q(V) are the elements of V, and {ū, v?} is an edge of Q(V) if and only if no other w? ? V agrees with ū in all the positions in which v? does. If V represents the set of keys for a statistical data base in which queries that match only one key are rejected, then the security of the individual data is related to the graph Q(V). Ernst Leiss showed that graphs belonging to any of several classes could be represented as query graphs and asked whether any connected graph could be so represented. We answer his question in the affirmative by making use of a spanning tree with special properties.     

Multipartite graph—Sparse graph Ramsey numbers

The Ramsey numberr(F, G) is determined in the case whereF is an arbitrary fixed graph andG is a sufficiently large sparse connected graph with a restriction on the maximum degree of its vertices. An asymptotically correct upper bound is obtained forr(F, T) whereT is a sufficiently large, but otherwise arbitrary, tree.     

Transforming a graph into a 1-balanced graph

Let G be a non-trivial, loopless graph and for each non-trivial subgraph H of G, let . The graph G is 1-balanced if γ(G), the maximum among g(H), taken over all non-trivial subgraphs H of G, is attained when H=G. This quantity γ(G) is called the fractional arboricity of the graph G. The value γ(G) appears in a paper by Picard and Queyranne and has been studied extensively by Catlin, Grossman, Hobbs and Lai. The quantity γ(G)−g(G) measures how much a given graph G differs from being 1-balanced. In this paper, we describe a systematic method of modifying a given graph to obtain a 1-balanced graph on the same number of vertices and edges. We obtain this by a sequence of iterations; each iteration re-defining one end-vertex of an edge in the given graph. After each iteration, either the value γ of the new graph formed is less than that of the graph from the previous iteration or the size of the maximal γ-achieving subgraph of the new graph is smaller than that of the graph in the previous iteration. We show that our algorithm is polynomial in time complexity. Further ways to decrease the number of iterations are also discussed.     

Connections between generalized graph entropies and graph energy

Dehmer and Mowshowitz introduced a class of generalized graph entropies using known information‐theoretic measures. These measures rely on assigning a probability distribution to a graph. In this article, we prove some extremal properties of such generalized graph entropies by using the graph energy and the spectral moments. Moreover, we study the relationships between the generalized graph entropies and compute the values of the generalized graph entropies for special graph classes. © 2014 Wiley Periodicals, Inc. Complexity 21: 35–41, 2015     

Transformation graph

The transformation graph G^-+- of a graph G is the graph with vertex set V(G)E(G), in which two vertices u and v are joined by an edge if one of the following conditions holds: (i) u,vV(G) and they are not adjacent in G, (ii) u,vE(G) and they are adjacent in G, (iii) one of u and v is in V(G) while the other is in E(G), and they are not incident in G. In this paper, for any graph G, we determine the connectivity and the independence number of G^-+-. Furthermore, for a graph G of order n4, we show that G^-+- is hamiltonian if and only if G is not isomorphic to any graph in {2K₁+K₂,K₁+K₃}{K_1,n-1,K_1,n-1+e,K_1,n-2+K₁}.     

The asymptotic probability that a random graph is a unit interval graph,indifference graph,or proper interval graph

Let G be a graph on v labelled vertices with E edges, without loops or multiple edges. Let v → ∞ and let E=E(v) be a function of v such that lim $\text{E(v)}\text{v}{}^{\mathrm{<mtext>2</mtext><mtext>3</mtext>}}\text{=c}$. The limit of the probability that a random graph is a unit interval graph, indifference graph or proper interval graph is exp(?$\text{4}\text{3}$c³).     

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.     

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...     

Indecomposability graph and critical vertices of an indecomposable graph

Given a directed graph G=(V,A), the induced subgraph of G by a subset X of V is denoted by G[X]. A subset X of V is an interval of G provided that for a,b∈X and x∈V?X, (a,x)∈A if and only if (b,x)∈A, and similarly for (x,a) and (x,b). For instance, 0?, V and {x}, x∈V, are intervals of G, called trivial intervals. A directed graph is indecomposable if all its intervals are trivial, otherwise it is decomposable. Given an indecomposable directed graph G=(V,A), a vertex x of G is critical if G[V?{x}] is decomposable. An indecomposable directed graph is critical when all its vertices are critical. With each indecomposable directed graph G=(V,A) is associated its indecomposability directed graph defined on V by: given x≠y∈V, (x,y) is an arc of if G[V?{x,y}] is indecomposable. All the results follow from the study of the connected components of the indecomposability directed graph. First, we prove: if G is an indecomposable directed graph, which admits at least two non critical vertices, then there is x∈V such that G[V?{x}] is indecomposable and non critical. Second, we characterize the indecomposable directed graphs G which have a unique non critical vertex x and such that G[V?{x}] is critical. Third, we propose a new approach to characterize the critical directed graphs.     

Between the enhanced power graph and the commuting graph

The purpose of this note is to define a graph whose vertex set is a finite group $G$, whose edge set is contained in that of the commuting graph of $G$ and contains the enhanced power graph of $G$. We call this graph the deep commuting graph of $G$. Two elements of $G$ are joined in the deep commuting graph if and only if their inverse images in every central extension of $G$ commute. We give conditions for the graph to be equal to either of the enhanced power graph and the commuting graph, and show that automorphisms of $G$ act as automorphisms of the deep commuting graph.     

Applications of ordinary voltage graph theory to graph embeddability

Let p be a prime greater than 5. We show that, while the generalized Petersen graphs of the form have cellular toroidal embeddings, they have no such embeddings having the additional property that a free action of a group on the graph extends to a cellular automorphism of the torus. Such an embedding is called a derived embedding. We also show that does have a derived embedding in the torus, and we show that for any odd q, each generalized Petersen graph of the form has a derived embedding in the Klein bottle, which has the same Euler characteristic as the torus. We close with some comments that frame these results in the light of Abrams and Slilaty's recent work on graphs featuring group actions that extend to spherical embeddings of those graphs.     

On the line graph of the complete tripartite graph

It is shown that the line graph of the complete tripartite graphK_n,n,n is characterized by the spectrum of its adjacency matrix.     

Full duality among graph algebras and flat graph algebras

We prove that among finite graph algebras and among finite flat graph algebras, dualizability, full dualizability, strong dualizability and entropicity are all equivalent. Any finite (flat) graph algebra which is not dualizable must be inherently non--dualizable for every infinite cardinal . A new, general method for proving strong duality is presented. Received August 30, 1999; accepted in final form September 22, 1999.     

Consistency and the graph Banzhaf value for communication graph games

The graph Banzhaf value was introduced and axiomatically characterized by Alonso-Meijide and Fiestras-Janeiro (2006). In this paper we propose the reduced game and consistency of the graph Banzhaf value for communication situations. By establishing the relationship between the Harsanyi dividends of a coalition in a communication situation and the reduced communication situation, we provide a new axiomatization of the graph Banzhaf value by means of the axioms of consistency and standardness.