Profile minimization on products of graphs (Q2495515): Difference between revisions

A proper numbering or a linear layout of a graph \(G = (V, E)\) with \(n\) vertices is a bijection \(f\) from \(V\) onto \(\{ 1, 2, \dots, n \}\). The profile width \(w_f(v)\) of a vertex \(v\) in \(G\) for a layout \(f\) is \(w_f(v) = f(v) - \min_{x \in N[v]} f(x)\), where \(N[v] = \{ v \} \cup \{ u \in V: uv \in E \}\). The profile \(P_f(G)\) of a layout \(f\) of \(G\) is \(P_f(G) = \sum_{v \in V} w_f(v)\), and the profile \(P(G)\) of \(G\) is \(P(G) = \min \{ P_f(G) : f\) is a linear layout of \(G \}\). The authors give a nice explanation of \(P(G) = \min \{| E(H)| : H\) is an interval supergraph of \(G \}\) appeared in \textit{Y. Lin} and \textit{J. Yuan} [Acta Math. Appl. Sin., Engl. Ser. 10, No. 1, 107--112 (1994; Zbl 0804.05060)]. \textit{P. A. Golovach} and \textit{F. V. Fomin} [Discrete Math. Appl. 8, No. 1, 73--80 (1998; Zbl 0965.05060)] proved that \(P(G) = \min \{\text{sc}(f, G): f\) is a linear layout of \(G \}\), where \(\text{sc}(f, G) = \sum_{i=1}^n | \{ u \in V: f(u) \leq i, f(v) > i\) for some \(v \in N[u] \}| \) is the total vertex separation number or the sum cut of \(G\). In this paper, the authors also obtain the profiles of \(K_m \times K_n\), \(K_{s,t} \times K_n\) and \(P_m \times K_n\), where \(K_n\) and \(P_n\) are the complete graph and the path on \(n\) vertices, respectively, \(K_{s,t}\) is the complete bipartite graph with partite sets of order \(s\) and \(t\), and the direct product \(G \times H\) has vertex set \(\{ (a, b): a \in V(G), b \in V(H) \}\) with \((a, b)\) adjacent to \((a', b')\) if \(aa' \in E(G)\) and \(bb' \in E(H)\).