A characterization of robert's inequality for boxicity

F.S. Roberts defined the boxicity of a graph G as the smallest positive integer n for which there exists a function F assigning to each vertex x?G a sequence F(x)(1),F(x)(2),…, F(x)(n) of closed intervals of R so that distinct vertices x and y are adjacent in G if and only if F(x)(i)∩F(y)(i)≠? fori = 1, 2, 3, …, n. Roberts then proved that if G is a graph having 2n + 1 vertices, thentheboxicityofGisatmostn. In this paper, we provide an explicit characterization of this inequality by determining for each n ? 1 the minimum collection $\text{C}$_n of graphs so that a graph G having 2n + 1 vertices has boxicity n if and only if it contains a graph from $\text{C}$_n as an induced subgraph. We also discuss combinatorial connections with analogous characterization problems for rectangle graphs, circular arc graphs, and partially ordered sets.     

Construction of matroidal families by partly closed sets

A matroidal family of graphs is a set $\text{M}$≠Ø of connected finite graphs such that for every finite graph G the edge sets of those subgraphs of G which are isomorphic to some element of $\text{M}$ are the circuits of a matroid on the edge set of G. In [9], Schmidt shows that, for n?0, ?2n<r?1, n, $\text{r∈}\text{Z}$, the set $\text{M}\text{(n, r)={G∣G}$ is a graph with β(G)=nα(G)+r and α(G )>, and is minimal with this property (with respect to the relation ?))} is a matroidal family of graphs. He also describes a method to construct new matroidal families of graphs by means of so-called partly closed sets. In this paper, an extension of this construction is given. By means of s-partly closed subsets of $\text{M}\text{(n, r)}$, s?r, we are able to give sufficient and necessary conditions for a subset $\text{P}\text{(n, r)}$ of $\text{M}\text{(n, r)}$ to yield a matroidal family of graphs when joined with the set $\text{I}\text{(n, s)}$ of all graphs $\text{G∈}\text{M}\text{(n, s)}$ which satisfy: If $\text{H∈}\text{P}\text{(n, r)}$, then H?G. In particular, it is shown that $\text{M}\text{(n, r)}$ is not a matroidal family of graphs for r?2. Furthermore, for n?0, 1?2n<r, n, $\text{r∈}\text{Z}$, the set of bipartite elements of $\text{M}\text{(n, r)}$ can be used to construct new matroidal families of graphs if and only if s?min(n+r, 1).     

Graph equations for line graphs,total graphs,middle graphs and quasi-total graphs

Let G be a graph with vertex-set V(G) and edge-set X(G). Let L(G) and T(G) denote the line graph and total graph of G. The middle graph M(G) of G is an intersection graph Ω(F) on the vertex-set V(G) of any graph G. Let F = V′(G) ∪ X(G) where V′(G) indicates the family of all one-point subsets of the set V(G), then $\text{M(G) = Ω(F)}$.The quasi-total graph P(G) of G is a graph with vertex-set V(G)∪X(G) and two vertices are adjacent if and only if they correspond to two non-adjacent vertices of G or to two adjacent edges of G or to a vertex and an edge incident to it in G.In this paper we solve graph equations $\text{L(G) ? P(H);}\text{L(G)}\text{? P(H); P(G) ? T(H);}\text{P(G)}\text{? T(H); M(G) ? P(H);}\text{M(G)}\text{? P(H)}$.     

Balancing signed graphs

A signed graph based on F is an ordinary graph F with each edge marked as positive or negative. Such a graph is called balanced if each of its cycles includes an even number of negative edges. Psychologists are sometimes interested in the smallest number d=d(G) such that a signed graph G may be converted into a balanced graph by changing the signs of d edges. We investigate the number D(F) defined as the largest d(G) such that G is a signed graph based on F. We prove that $\text{1}\text{2}\text{m?}\text{nm}\text{≤D(F)≤}\text{1}\text{2}\text{m}$ for every graph F with n vertices and m edges. If F is the complete bipartite graph with t vertices in each part, then $\text{D(F)≤}\text{1}\text{2}\text{t}{}^2\text{?ct}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}$ for some positive constant c.     

Comparability graphs and intersection graphs

A function diagram (f-diagram) D consists of the family of curves {$\text{1}\text{?}$ñ} obtained from n continuous functions $\text{f}{}_{\mathrm{i}}\text{:[0,1]→}\text{R}\text{(1?i?n)}$. We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the f_i are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of $\text{G}\text{?}\text{is ?k+1}$. Computational complexity results are obtained for recognizing such graphs.     

Complexity of representation of graphs by set systems

Let $\text{F}$ be a family of subsets of S and let G be a graph with vertex set $\text{V={x}{}_{\mathrm{A}}\text{|A ∈}\text{F}\text{}}$ such that: (x_A, x_B) is an edge iff $\text{A?B≠}\text{0}\text{/}$. The family $\text{F}$ is called a set representation of the graph G.It is proved that the problem of finding minimum k such that G can be represented by a family of sets of cardinality at most k is NP-complete. Moreover, it is NP-complete to decide whether a graph can be represented by a family of distinct 3-element sets.The set representations of random graphs are also considered.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

The frame dimension and the complete overlap dimension of a graph

Roberts (F. S. Roberts, On the boxicity and cubicity of a graph. In Recent Progress in Combinatorics, W. T. Tutte, ed. Academic, New York (1969)), studied the intersection graphs of closed boxes (products of closed intervals) in Euclidean n-space, and introduced the concept of the boxicity of a graph G, the smallest n such that G is the intersection graph of boxes in n-space. In this paper, we study the intersection graphs of the frames or boundaries of such boxes. We study the frame dimension of a graph G—the smallest n such that G is the intersection graph of frames in n-space. We also study the complete overlap dimension of a graph, a notion that is almost equivalent. The complete overlap dimension of a graph G is the smallest dimension in which G can be represented by boxes that intersect but are not completely contained in one another. We will prove that these dimensions are in almost all cases the same and that they both can become arbitrarily large. We shall also obtain a bound for these dimensions in terms of boxicity.     

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

Convex polyhedra of doubly stochastic matrices: II. Graph of Ωn

Properties of the graph $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ of the polytope $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices are studied. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is not a k-dimensional rectangular parallelotope for k ≥ 2, then G($\text{F}$) is Hamilton connected. Prime factor decompositions of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ relative to Cartesian product are investigated. In particular, if $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then the number of prime graphs in any prime factor decomposition of G($\text{F}$) equals the number of connected components of the neighborhood of any vertex of G($\text{F}$). Distance properties of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ are obtained. Faces $\text{F}$ of $\text{Ω}{}_{\mathrm{n}}$ for which G($\text{F}$) is a clique of $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ are investigated.     

Lower bounds on the independence number in terms of the degrees

Wei discovered that the independence number of a graph G is at least Σ_v(1 + d(v))^?1. It is proved here that if G is a connected triangle-free graph on n ≥ 3 vertices and if G is neither an odd cycle nor an odd path, then the bound above can be increased by $\text{n}\text{Δ(Δ + 1)}$, where Δ is the maximum degree. This new bound is sharp for even cycles and for three other graphs. These results relate nicely to some algorithms for finding large independent sets. They also have a natural matrix theory interpretation. A survey of other known lower bounds on the independence number is presented.     

Extremal values of the interval number of a graph,II

It is shown that the interval number of a graph on n vertices is at most $\text{[}\text{1}\text{4}\text{(n+1)]}$, and this bound is best possible. This means that we can represent any graph on n vertices as an intersection graph in which the sets assigned to the vertices each consist of the union of at most $\text{[}\text{1}\text{4}\text{(n+1)]}$ finite closed intervals on the real line. This upper bound is attained by the complete bipartite graph K_[n/2],[n/2].     

A note on the similarity depth

In this note we demonstrate the existence of E0L forms F and G which are n-similar, i.e. $\text{L}$ⁿ(F) = $\text{L}$ⁿ(G) but $\text{L}$ⁿ⁺¹(F)≠$\text{L}$ⁿ⁺¹(G) for n ∈ {2, 3}. This partially solves an open problem from [3].     

On a general class of graph polynomials

Let $\text{F}$ be a family of connected graphs. With each element α ∈ $\text{F}$, we can associate a weight w_α. Let G be a graph. An F-cover of G is a spanning subgraph of G in which every component belongs to $\text{F}$. With every F-cover we can associate a monomial π(C) = Π_αw_α, where the product is taken over all components of the cover. The F-polynomial of G is Σπ(C), where the sum is taken over all F-covers in G. We obtain general results for the complete graph and complete bipartite graphs, and we show that many of the well-known graph polynomials are special cases of more general F-polynomials.     

On k-sequential and other numbered graphs

The concept of a k-sequential graph is presented as follows. A graph G with ∣V(G)∪ E(G)∣=t is called k-sequential if there is a bijection$\text{?: V(G)∪E(G) → {k,k+1,…,t+k?1}}$ such that for each edge$\text{e}\text{?}\text{=xy}$in E(G) one has$\text{?(}\text{e}\text{?}\text{) = ∣?(x)??(y)∣}$. A graph that is 1-sequential is called simply sequential, and, in particular the author has conjectured that all trees are simply sequential. In this paper an introductory study of k-sequential graphs is made. Further, several variations on the problems of gracefully or sequentially numbering the elements of a graph are discussed.     

Small diameter interchange graphs of classes of matrices of zeros and ones

Let $\text{A}$(R, S) denote the class of all m×n matrices of 0's and 1's having row sum vector R and column sum vector S. The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{A}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We characterize those $\text{A}$(R, S) for which the graph G(R, S) has diameter at most 2 and those $\text{A}$(R, S) for which G(R, S) is bipartite.     

Hamiltonicity in (0–1)-polyhedra

The graph G(P) of a polyhedron P has a node corresponding to each vertex of P and two nodes are adjacent in G(P) if and only if the corresponding vertices of P are adjacent on P. We show that if P ? $\text{R}$ⁿ is a polyhedron, all of whose vertices have (0–1)-valued coordinates, then (i) if G(P) is bipartite, the G(P) is a hypercube; (ii) if G(P) is nonbipartite, then G(P) is hamilton connected. It is shown that if P ? $\text{R}$ⁿ has (0–1)-valued vertices and is of dimension d (≤n) then there exists a polyhedron P′ ? $\text{R}$^d having (0–1)-valued vertices such that $\text{G(P) ? G(P′)}$. Some combinatorial consequences of these results are also discussed.     

Minimum number of edges in graphs that are both P2- and Pi-connected

A simple graph with n vertices is called P_i-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both P₂- and P_i-connected are obtained. Namely if $\text{i?}\text{1}\text{2}\text{(n+1)}$, then |E(G)|?((4i?5)/(2i?2))(n?1), and if $\text{i >}\text{1}\text{2}\text{(n+ 1)}$, then |E(G)|?2(n?1) apart from one exeptional graph. Furthermore, extremal graphs are determined in the former.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.