Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
3 results
Search Results
Item Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two(Hindawi Limited, 2018) Kola, S.R.; Gudla, B.; Niranjan, P.K.An L(2,1)-coloring of a simple connected graph G is an assignment f of nonnegative integers to the vertices of G such that fu-fv2 if d(u,v)=1 and fu-fv1 if d(u,v)=2 for all u,v∈V(G), where d(u,v) denotes the distance between u and v in G. The span of f is the maximum color assigned by f. The span of a graph G, denoted by (G), is the minimum of span over all L(2,1)-colorings on G. An L(2,1)-coloring of G with span (G) is called a span coloring of G. An L(2,1)-coloring f is said to be irreducible if there exists no L(2,1)-coloring g such that g(u)f(u) for all u∈V(G) and g(v)Item Gallai’s Path Decomposition for 2-degenerate Graphs(Discrete Mathematics and Theoretical Computer Science, 2023) Anto, N.; Basavaraju, M.Gallai’s path decomposition conjecture states that if G is a connected graph on n vertices, then the edges of G can be decomposed into at most ⌈ n2 ⌉ paths. A graph is said to be an odd semi-clique if it can be obtained from a clique on 2k + 1 vertices by deleting at most k − 1 edges. Bonamy and Perrett asked if the edges of every connected graph G on n vertices can be decomposed into at most ⌊ n2 ⌋ paths unless G is an odd semi-clique. A graph G is said to be 2-degenerate if every subgraph of G has a vertex of degree at most 2. In this paper, we prove that the edges of any connected 2-degenerate graph G on n vertices can be decomposed into at most ⌊ n2 ⌋ paths unless G is a triangle. © 2023 by the author(s)Item An improved upper bound for the domination number of a graph(Springer, 2025) Arumugam, S.; Hegde, S.M.; Kulamarva, S.Let G be a graph of order n. A classical upper bound for the domination number of a graph G having no isolated vertices is ?n2?. However, for several families of graphs, we have ?(G)??n? which gives a substantially improved upper bound. In this paper, we give a condition necessary for a graph G to have ?(G)??n?, and some conditions sufficient for a graph G to have ?(G)??n?. We also present a characterization of all connected graphs G of order n with ?(G)=?n?. Further, we prove that for a graph G not satisfying rad(G)=diam(G)=rad(G¯)=diam(G¯)=2, deciding whether ?(G)??n? or ?(G¯)??n? can be done in polynomial time. We conjecture that this decision problem can be solved in polynomial time for any graph G. © Indian Academy of Sciences 2025.