On unretractive graphs

The present paper proves necessary and sufficient conditions for both lexicographic products and arbitrary graphs to be unretractive. The paper also proves that the automorphism group of a lexicographic product of graphs is isomorphic to a wreath product of a monoid with a small category.     

A proof of a conjecture of Sabidussi on graphs idempotent under the lexicographic product

In 1960, Sabidussi conjectured that if a graph G is isomorphic to the lexicographic product G[G], then the wreath product of by itself is a proper subgroup of . A positive answer is provided by constructing an automorphism Ψ of G[G] which satisfies: for every vertex x of G, there is an infinite subset I(x) of V(G) such that Ψ({x}×V(G))=I(x)×V(G).     

Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs

Consider two graphs $G$ and $H$. Let $H^k\left[G\right]$ be the lexicographic product of $H^k$ and $G$, where $H^k$ is the lexicographic product of the graph $H$ by itself $k$ times. In this paper, we determine the spectrum of $H^k\left[G\right]$ and $H^k$ when $G$ and $H$ are regular and the Laplacian spectrum of $H^k\left[G\right]$ and $H^k$ for $G$ and $H$ arbitrary. Particular emphasis is given to the least eigenvalue of the adjacency matrix in the case of lexicographic powers of regular graphs, and to the algebraic connectivity and the largest Laplacian eigenvalues in the case of lexicographic powers of arbitrary graphs. This approach allows the determination of the spectrum (in case of regular graphs) and Laplacian spectrum (for arbitrary graphs) of huge graphs. As an example, the spectrum of the lexicographic power of the Petersen graph with the googol number (that is, 10¹⁰⁰ ) of vertices is determined. The paper finishes with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

The geodetic number of the lexicographic product of graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in an interval between two vertices from S. The size of a minimum geodetic set in G is the geodetic number g(G) of G. We find that the geodetic number of the lexicographic product G°H for a non-complete graph H lies between 2 and 3g(G). We characterize the graphs G and H for which g(G°H)=2, as well as the lexicographic products T°H that enjoy g(T°H)=3g(G), when T is isomorphic to a tree. Using a new concept of the so-called geodominating triple of a graph G, a formula that expresses the exact geodetic number of G°H is established, where G is an arbitrary graph and H a non-complete graph.     

On the ultimate lexicographic Hall-ratio

The Hall-ratio ρ(G) of a graph G is the ratio of the number of vertices and the independence number maximized over all subgraphs of G. The ultimate lexicographic Hall-ratio of a graph G is defined as , where G^°n denotes the nth lexicographic power of G (that is, n times repeated substitution of G into itself). Here we prove the conjecture of Simonyi stating that the ultimate lexicographic Hall-ratio equals the fractional chromatic number for all graphs.     

Hamilton cycle decompositions of the tensor products of complete bipartite graphs and complete multipartite graphs

In this paper, it is shown that the tensor product of the complete bipartite graph, K_r,r,r≥2, and the regular complete multipartite graph, , is Hamilton cycle decomposable.     

On the number of graphs with a given endomorphism monoid

For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then .     

广义字典序积的自同态幺半群

讨论了图的广义字典序积的自同态幺半群的性质,给出了广义字典序积图X[Yz|x∈V（X）]的自同态幺半群与X,Yx(x∈V(X))的自同态幺半群的圈积相等的充要条件。     

On optimizing edge connectivity of product graphs

This work studies the super edge connectivity and super restricted edge connectivity of direct product graphs, Cartesian product graphs, strong product graphs and lexicographic product graphs. As a result, sufficient conditions for optimizing the edge connectivity and restricted edge connectivity of these graphs are presented.     

On anti-magic labeling for graph products

An anti-magic labeling of a finite simple undirected graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1,2,…,q} such that the vertex sums are pairwise distinct, where the vertex sum at one vertex is the sum of labels of all edges incident to such vertex. A graph is called anti-magic if it admits an anti-magic labeling. Hartsfield and Ringel conjectured in 1990 that all connected graphs except K₂ are anti-magic. Recently, Alon et al. showed that this conjecture is true for dense graphs, i.e. it is true for p-vertex graphs with minimum degree Ω(logp). In this article, new classes of sparse anti-magic graphs are constructed through Cartesian products and lexicographic products.     

Foundations of lexicographic utility

This paper presents an alternative mathematical characterization of lexicographic utility to the one given by Chipman (1960). A natural constructivistic procedure on imposing a lexicographic ordering on the product space of natural numbers is pursued. The consequences on the topological structure of such a space are examined.     

Decomposition tree of a lexicographic product of binary structures

Given a set S and a positive integer k, a binary structure is a function . The set S is denoted by V(B) and the integer k is denoted by . With each subset X of V(B) associate the binary substructure B[X] of B induced by X defined by B[X](x,y)=B(x,y) for any x≠y∈X. A subset X of V(B) is a clan of B if for any x,y∈X and v∈V(B)?X, B(x,v)=B(y,v) and B(v,x)=B(v,y). A subset X of V(B) is a hyperclan of B if X is a clan of B satisfying: for every clan Y of B, if X∩Y≠0?, then X⊆Y or Y⊆X. With each binary structure B associate the family Π(B) of the maximal proper and nonempty hyperclans under inclusion of B. The decomposition tree of a binary structure B is constituted by the hyperclans X of B such that Π(B[X])≠0? and by the elements of Π(B[X]). Given binary structures B and C such that , the lexicographic product B⌊C⌋ of C by B is defined on V(B)×V(C) as follows. For any (x,y)≠(x^′,y^′)∈V(B)×V(C), B⌊C⌋((x,x^′),(y,y^′))=B(x,y) if x≠y and B⌊C⌋((x,x^′),(y,y^′))=C(x^′,y^′) if x=y. The decomposition tree of the lexicographic product B⌊C⌋ is described from the decomposition trees of B and C.     

Retractions of split graphs and End-orthodox split graphs

A retraction f of a graph G is an edge-preserving mapping of G with f(v)=v for all v∈V(H), where H is the subgraph induced by the range of f. A graph G is called End-orthodox (End-regular) if its endomorphism monoid End X is orthodox (regular) in the semigroup sense. It is known that a graph is End-orthodox if it is End-regular and the composition of any two retractions is also a retraction. The retractions of split graphs are given and End-orthodox split graphs are characterized.     

Graphical complexity of products of permutation groups

In this paper we study representations of permutation groups as automorphism groups of colored graphs and supergraphs. In particular, we consider how such representations for various products of permutation groups can be obtained from representations of factors and how the degree of complexity increases in such constructions.     

On lexicographic optimal solutions in transportation problems

Lexicographic versions of the cost minimizing transportation problem (CMTP) and the time minimizing transportation problem (TMTP) are presented in this paper. In addition to minimizing the quantity sent on the costliest routes in a cost minimizing transportation problem. an attempt is made to minimize the quantity transported on the second-costliest routes. if the shipment on the costliest routes is as small as possible and the quantity shipped on the third-costliest routes, if the shipments on the costliest and the second- costliest routes are as small as possible. and so on. In a lexicographic time minimizing transportation problem one is not only interested in minimizing the transportation cost on the routes of the longest duration but also on the routes of second longest, third-longest duration and so on. For finding lexicographic optimal solutions (LOS) of lexicographic cost minimizing and time minimizing transportation problems a standard cost minimizing transportation problem is formulated whose optimal solution is shown to provide the answer. Some extensions are also discussed     

The fractional chromatic number, the Hall ratio, and the lexicographic product

Let χ_f denote the fractional chromatic number and ρ the Hall ratio, and let the lexicographic product of G and H be denoted GlexH. Main results: (i) ρ(GlexH)≤χ_f(G)ρ(H); (ii) if ρ(G)=χ_f(G) then ρ(GlexH)=ρ(G)ρ(H) for all H; (iii) χ_f−ρ is unbounded. In addition, the question of how big χ_f/ρ can be is discussed.     

Hamilton cycle decompositions of the tensor product of complete multipartite graphs

In this paper, tensor product of two regular complete multipartite graphs is shown to be Hamilton cycle decomposable. Using this result, it is immediate that the tensor product of two complete graphs with at least three vertices is Hamilton cycle decomposable thereby providing an alternate proof of this fact.     

On G-locally primitive graphs of locally Twisted Wreath type and a conjecture of Weiss

Let Γ be a connected G-vertex-transitive graph and let v be a vertex of Γ. The graph Γ is said to be G-locally primitive if the action of the vertex-stabiliser Gv on the neighbourhood Γ(v) of v is primitive. Furthermore, Γ is said to be of locally Twisted Wreath type if Gv is a primitive group of Twisted Wreath type in its action on Γ(v).Richard Weiss conjectured in 1978 that, there exists a function f:N→N such that if Γ is a connected G-vertex-transitive locally primitive graph of valency d and v is a vertex of Γ, then |Gv|?f(d). In this paper we prove this conjecture when Γ is of locally Twisted Wreath type.