POLYNOMIAL-TIME APPROACHES TO FUZZINESS IN RATIO LABELLED GENERAL GRAPHS

In classical fuzzy graph theory, fuzziness is introduced by freely assigning membership values to vertices and edges, which makes every crisp graph trivially fuzzy. To avoid this limitation, we propose ratio labeling (RL), a structured labelling scheme in which vertex and edge memberships are linked by a fixed functional relationship. This approach provides a meaningful and non-trivial criterion for deciding when a graph can truly be considered fuzzy. We derive necessary and sufficient conditions under which a crisp graph becomes a fuzzy graph under ratio labelling and characterize the class of general graphs that admit fuzziness in this framework. We also present deterministic polynomial-time algorithms to label the vertices and edges of a general graph and to determine whether a given graph admits fuzziness under ratio labelling. These results offer an efficient and systematic method for studying fuzziness in general graphs and highlight the potential of ratio labelling for applications in connectivity analysis.