A split graph is a graph in which the vertices can be partitioned into an independent set and a clique. We show that every nonsplit graph has at most four split maximal proper edge induced subgraphs. The exhaustive list of fifteen classes of nonsplit graphs having a split maximal proper edge induced subgraph is determined in this paper.

A kernel \(J\) of a digraph \(D\) is an independent set of vertices of \(D\) such that for every \(z\in V(D)\backslash J\) there exists an arc from \(z\) to \(J.\) A digraph \(D\) is said to be kernel-perfect if every induced subdigraph of it has a kernel. We characterise kernel-perfectness in special families of digraphs, namely, the line digraph, the subdivision digraph, the middle digraph, the digraph \(R(D)\) and the total digraph. We also obtain some results on kernel-perfectness in the generalised Mycielskian of digraphs. Moreover, we find some new classes of kernel-perfect digraphs by introducing a new product on digraphs.

The first, second Zagreb connection indices and modified first Zagreb connection index are defined as \(Z{C_1}(G)={\sum\limits_{{v\in V(G)}} {{\tau _G}^2(v)} }\), \(ZC{}_{2}(G)=\displaystyle\sum_{uv\in E(G)}^{}\tau{}_{G}(u)\tau{}_{G}(v)\) and \(ZC{}_{1}^{\ast }(G)=\displaystyle\sum_{v\in V(G)}^{}d{}_{G}(v)\tau{}_{G}(v)\), respectively. In this paper, we consider the maximum values of \(Z{C_1}(G)\), \(Z{C_2}(G)\), \(Z{C_1}^{*}(G)\) of \(n\)-vertex trees with fixed matching number \(m\) and the extremal graphs are also characterized.

An improper interval (edge) coloring of a graph \(G\) is an assignment of integer colors to the edges of \(G\) satisfying the condition that, for every vertex \(v \in V(G)\), the set of colors assigned to the edges incident with \(v\) forms an integral interval. An interval coloring is \(k\)-improper if at most \(k\) edges with the same color all share a common endpoint. The minimum integer \(k\) such that there exists a \(k\)-improper interval coloring of the graph \(G\) is the interval coloring impropriety of \(G\), denoted by \(\mu_{int}(G)\). In this paper, we provide a construction of an interval coloring of a subclass of complete multipartite graphs. Additionally, we determine improved upper bounds on the interval coloring impropriety of several classes of graphs, namely 2-trees, iterated triangulations, and outerplanar graphs. Finally, we investigate the interval coloring impropriety of the corona product of two graphs, \(G\odot H\).

A decomposition \(\mathcal{C}\) of a graph \(G\) is primitive if no proper, nontrivial subset of \(\mathcal{C}\) is a decomposition of an induced subgraph of \(G\). The existence of primitive decompositions has been studied for several decompositions, including path and cycle decompositions for complete and cocktail party graphs. In this work, we classify the existence of primitive star decompositions for complete graphs.

In this paper, we study the distribution on \([k]^n\) for the parameter recording the number of indices \(i \in [n-1]\) within a word \(w=w_1\cdots w_n\) such that \(|w_{i+1}-w_i|\ \leq 1\) and compute the corresponding (bivariate) generating function. A circular version of the problem wherein one considers whether or not \(|w_n-w_1|\ \leq 1\) as well is also treated. As special cases of our results, one obtains formulas involving staircase and Hertzsprung words in both the linear and circular cases. We make use of properties of special matrices in deriving our results, which may be expressed in terms of Chebyshev polynomials. A generating function formula is also found for the comparable statistic on finite set partitions with a fixed number of blocks represented sequentially.

Let \(G=(V,E)\) be a graph of order \(n\) without isolated vertices. A bijection \(f\colon V\rightarrow \{1,2,\dots,n\}\) is called a local distance antimagic labeling, if \(w(u)\not=w(v)\) for every edge \(uv\) of \(G\), where \(w(u)=\sum_{x\in N(u)}f(x)\). The local distance antimagic chromatic number \(\chi_{ld}(G)\) is defined to be the minimum number of colors taken over all colorings of \(G\) induced by local distance antimagic labelings of \(G\). The concept of Generalized Mycielskian graphs was introduced by Stiebitz [20]. In this paper, we study the local distance antimagic labeling of the Generalized Mycielskian graphs.

A graph is called \(t\)-existentially closed (\(t\)-e.c.) if it satisfies the following adjacency property: for every \(t\)-element subset \(A\) of the vertices, and for every subset \(B \subseteq A\), there exists a vertex \(x \in A\) that is adjacent to all vertices in \(B\) and to none of the vertices in \(A \setminus B\). A \(t\)-e.c. graph is critical if removing any single vertex results in a graph that is no longer \(t\)-e.c. This paper investigates \(2\)-e.c. critical Cayley graphs and vertex-transitive graphs, providing explicit constructions of \(2\)-e.c. critical Cayley graphs on cyclic groups. It is shown that a \(2\)-e.c. critical Cayley graph (as well as vertex-transitive graphs) of order \(n\) exists if and only if \(n \geq 9\) and \(n \notin \{10, 11, 14\}\). Additionally, this paper examines the numbers of \(2\)-e.c. (critical) vertex-transitive graphs among all vertex-transitive graphs for small orders, and presents detailed observations on some \(2\)-e.c. and \(3\)-e.c. vertex-transitive graphs.

For a family \(\mathcal F\) of graphs, a graph \(G\) is said to be \(\mathcal F\)-free if \(G\) contains no member of \(\mathcal F\) as an induced subgraph. We let \(\mathcal G_{3}(\mathcal F)\) be the family of \(3\)-connected \(\mathcal F\) -free graphs. Let \(P_{n}\) and \(C_{n}\) denote the path and the cycle of order \(n\), respectively. Let \(T_{0}\) be the tree of order nine obtained by joining a pendant edge to the central vertex of \(P_{7}\). Let \(T_{1}\) and \(T_{2}\) be the trees of order ten obtained from \(T_{0}\) by joining a new vertex to a vertex of \(P_{7}\) adjacent to an endvertex, and to a vertex of \(P_{7}\) adjacent to the central vertex, respectively. We show that \(\mathcal G_{3}(\{C_{3}, C_{4}, T_{1}\})\) and \(\mathcal G_{3}(\{C_{3}, C_{4}, T_{2}\})\) are finite families.