Aug 2026· Mathematics· Vol 14, pp. 3006· 0 citations· 28 references
Abstract
The study of graph connectedness is a central topic in graph theory, with CF-connectedness being a specialized property of interest. A simple graph is CF-connected if it is connected and, in each of its optimal drawings, any two of its distinct vertices can be connected by a path consisting of uncrossed edges. This paper explores the CF-connectedness of complete bipartite graphs with one edge removed, denoted as Km,n∖e, where Km,n is a complete bipartite graph with partite sets of sizes m and n, while e is an arbitrary edge. We conjecture that Km,n∖e is CF-connected if and only if it contains no subgraph isomorphic to K3,7∖e or K4,5∖e. We verify this conjecture unconditionally for Km,n∖e with min{m,n}≤5. We also prove unconditionally that cr(K6,6∖e)=32, thereby confirming Chia and Lee’s conjecture in this case and showing that K6,6∖e is not CF-connected. For the remaining cases with larger partite sets, our results are conditional on Chia and Lee’s conjectured formula cr(Km,n∖e)=m2m−12n2n−12−m−12n−12. Assuming this formula, the proposed characterization of CF-connectedness extends to these cases.
Linear hypergraph set-indexers (LHSIs) associate a graph with a vertex hypergraph and an induced edge hypergraph through injective set-valuations and symmetric-difference edge labels. This study examines structural properties of graphs under LHSIs, with particular emphasis on conditions under which the associated verte...
Viji Paul, Saneesh Babu· Asian Research Journal of Ma...· 0 citations
Graph colouring is a fundamental concept in graph theory with diverse real-world applications. List colouring is a key concept in graph colouring where vertices are coloured using an available list of possible colours. Proper list colouring guarantees that no two adjacent vertices share the same colour. If every vertex...
G. G. B. R. Jayawardhana, G. S. Wijesiri, S. Almeida· Journal of the National Scie...· 0 citations
A graph is \emph{elementary} if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chv\'atal--Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipart...
N. Narayanan, Nandana K. Vasudevan, K. Somasundaram· 0 citations
The existence and construction of distance magic labelings for certain families of complete bipartite graphs are investigated to contribute to the understanding of how arithmetic structure and partition properties influence the existence of distance magic labelings.
Kaveesha V. Senarathna, Sujeeva Wijesiri, S. Almeida· Symmetry· 0 citations
In this paper, we study CONFLICT-FREE EDGE CUT (CF-CUT), which is a recently introduced conflict-free version of the MIN-CUT problem that asks to find the minimum number of edges to disconnect a connected graph. The CF-CUT takes as input a connected undirected graph G = (V, E), a conflict graph $\widehat{G}$ such that...
Sourav Das, Ashwin Jacob, Arpit Kumar et al.· 0 citations
A graph is called H-free if the graph has no subgraph being isomorphic to H. The classical Turán problem aims to determine the maximum size of an H-free graph with given order. In 2010, Nikiforov introduced the spectral Turán-type problem: determine the maximum spectral radius of an H-free graph with given order. He al...
Xiao-Bing Luo· Mathematical and Computation...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
