Search

Björner, Lovász and Shor introduced a chip-firing game on a finite graph $$G$$ as follows. We put some chips on each vertex of $$G$$ , we say that a vertex is ready if it has at least as many chips as its degree, in which case we can fire it and the result is that it distributes one chip to each of its neighbors, this may cause other vertices to be ready, and so on. This game continues until no vertex can be fired. In this paper, we study chip-firing games on complete graphs. We obtain a sufficient and necessary condition for chip-firing games on complete graphs to be finite. [ABSTRACT FROM AUTHOR]

The b-chromatic index $$\varphi '(G)$$ of a graph $$G$$ is the largest integer $$k$$ such that $$G$$ admits a proper $$k$$ -edge coloring in which every color class contains at least one edge incident to some edge in all the other color classes. The b-chromatic index of trees is determined and equals either to a natural upper bound $$m'(T)$$ or one less, where $$m'(T)$$ is connected with the number of edges of high degree. Some conditions are given for which graphs have the b-chromatic index strictly less than $$m'(G)$$ , and for which conditions it is exactly $$m'(G)$$ . In the last part of the paper, regular graphs are considered. It is proved that with four exceptions, the b-chromatic index of cubic graphs is $$5$$ . The exceptions are $$K_4$$ , $$K_{3,3}$$ , the prism over $$K_3$$ , and the cube $$Q_3$$ . [ABSTRACT FROM AUTHOR]

Let $$G$$ be a graph with degree sequence $$d_1,d_2,\ldots ,d_n$$ . Given a positive integer $$p$$ , denote by $$e_p(G)=\sum _{i=1}^n d_i^p$$ . Caro and Yuster introduced a Turán-type problem for $$e_p(G)$$ : given an integer $$p$$ , how large can $$e_p(G)$$ be if $$G$$ has no subgraph of a particular type. They got some results for the subgraph of particular type to be a clique of order $$r+1$$ and a cycle of even length, respectively. Denote by $$ex_p(n,H)$$ the maximum value of $$e_p(G)$$ taken over all graphs with $$n$$ vertices that do not contain $$H$$ as a subgraph. Clearly, $$ex_1(n,H)=2ex(n,H)$$ , where $$ex(n,H)$$ denotes the classical Turán number. In this paper, we consider $$ex_p(n, C_5)$$ and prove that for any positive integer $$p$$ and sufficiently large $$n$$ , there exists a constant $$c=c(p)$$ such that the following holds: if $$ex_p(n, C_5)=e_p(G)$$ for some $$C_5$$ -free graph $$G$$ of order $$n$$ , then $$G$$ is a complete bipartite graph having one vertex class of size $$cn+o(n)$$ and the other $$(1-c)n+o(n)$$ . [ABSTRACT FROM AUTHOR]

The energy of a simple graph $$G$$ , denoted by $$E(G)$$ , is defined as the sum of the absolute values of eigenvalues of $$G$$ . In this paper, we show that, among all subdivisions of graphs with $$n$$ vertices and chromatic number $$k$$ , the subdivision of the Turán graph $$T(n,k)$$ has the maximal energy. [ABSTRACT FROM AUTHOR]

The second Zagreb index of a graph G is an adjacency-based topological index, which is defined as Σuv∊E(G)(d(u)d(v)), where uv is an edge of G, d(u) is the degree of vertex u in G. In this paper, we consider the second Zagreb index for bipartite graphs. Firstly, we present a new definition of ordered bipartite graphs, and then give a necessary condition for a bipartite graph to attain the maximal value of the second Zagreb index. We also present an algorithm for transforming a bipartite graph to an ordered bipartite graph, which can be done in O(n2+n21) time for a bipartite graph B with a partition ∣X∣ = n1 and ∣Y∣ = n2. [ABSTRACT FROM AUTHOR]

A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. We show that every graph of order $$n\ge 9$$ and size at least $$\lfloor \frac{7n-13}{2}\rfloor $$ contains two disjoint theta graphs. We also show that every 2-edge-connected graph of order $$n\ge 6$$ and size at least $$3n-5$$ contains two disjoint cycles, such that any specified vertex with degree at least three belongs to one of them. The lower bound on size in both is sharp in general. [ABSTRACT FROM AUTHOR]