Abstract:Using coalescence and cones, this study defines three types of graphs formed by amalgamating vertices of disjoint unions of complete graphs. The three types include the cone over a disjoint union of two complete graphs (C1), the cone over a disjoint union of \(k\) complete graphs (C2), and the \(l\) cone over a disjoint union of two complete graphs (C3). Coalescence of complete graphs (C1, C3) and the \(l\) cone (C3) are determined by their Laplacian spectra, a novel finding. Their Laplacian spectra reveal the size of the vertex cutset. Applications include the analysis of corporate networks, where individuals form coalescence of complete graphs through joint membership of two or more company boards.

Abstract:A famous conjecture of Ryser states that any \(r\)-partite set system has transversal number at most \(r-1\) times their matching number. This conjecture is only known to be true for \(r\leq3\) in general, for \(r\leq5\) if the set system is intersecting, and for \(r\leq9\) if the set system is intersecting and linear. In this note, we deal with Ryser’s conjecture for intersecting \(r\)-partite linear systems: if \(\tau\) is the transversal number for an intersecting \(r\)-partite linear system, then \(\tau\leq r-1\). If this conjecture is true, this is known to be sharp for \(r\) for which there exists a projective plane of order \(r-1\). There has also been considerable effort to find intersecting \(r\)-partite set systems whose transversal number is \(r-1\). In this note, we prove that if \(r\geq2\) is an even integer, then \(f_l(r)\geq3r-5\), where \(f_l(r)\) is the minimum number of lines of an intersecting \(r\)-partite linear system whose transversal number is \(r-1\). Aharoni \emph{et al.,} [R. Aharoni, J. Barát and I.M. Wanless, \emph{Multipartite hypergraphs achieving equality in Ryser’s conjecture}, Graphs Combin. {\bf 32}, 1–15 (2016)] gave an asymptotic lower bound: \(f_l(r)\geq3\).\(052r+O(1)\) as \(r\to\infty\). For some small values of \(r\) (\(r\geq2\) an even integer), our lower bound is better. Also, we prove that any \(r\)-partite linear system satisfies \(\tau\leq r-1\) if \(\nu_2\leq r\) for all \(r\geq3\) odd integer and \(\nu_2\leq r-2\) for all \(r\geq4\) even integer, where \(\nu_2\) is the maximum cardinality of a subset of lines \(R\subseteq\mathcal{L}\) such that any three elements chosen in \(R\) do not have a common point.

Abstract:The vertex-degree based (VDB) topological index (or graphical function-index) \(TI_{f}(G)\) of \(G\) with edge-weight function \(f(x,y)\) was defined as \(TI_{f}(G)=\sum\limits_{uv\in E(G)}f(d(u),d(v))\), where \(d(u)\) is the degree of vertex \(u\) in \(G\). In this paper, we use a unified way to determine the extremal values of VDB indices of connected \((n,m)\)-graphs. When \(f(x,y)\) satisfies some special properties, we determine the connected \((n,m)\)-graphs with maximum (or minimum) \(TI_{f}(G)\) is the almost regular graphs. Our results generalize the results of paper [Aashtab, A., Akbari, S., Madadinia, S., Noei, M., \& Salehi, F. (2022) On the graphs with minimum Sombor index. MATCH Commun. Math. Comput. Chem., {88}, 553-559].

Abstract:For all positive even integers \(n\), graphs of order \(n\) with degree sequence \(S_{n}:1,2,\dots,n/2,n/2,n/2+1,n/2+2,\dots,n-1\) naturally arose in the study of a labeling problem in [1].This fact motivated the authors of the aforementioned paper to study these sequences and as a result of this study they proved that there is a unique graph of order \(n\) realizing \(S_{n}\) for every even integer \(n\). The main goal of this paper is to generalize this result.