Character degree graphs with no complete vertices

Let Γ be a graph in which each vertex is non-adjacent to another different one. We show that, if G is a finite solvable group with abelian Fitting subgroup and with character degree graph $\Gamma (G)=\Gamma$, then G is a direct product of subgroups having a disconnected character degree graph. In particular, Γ is a join of disconnected graphs. We deduce also that solvable groups with abelian Fitting subgroup have a character degree graph with diameter at most 2.     

A lower bound on the acyclic matching number of subcubic graphs

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$, that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices incident to edges in $M$ is a forest. We show that the acyclic matching number of a connected subcubic graph $G$ with $m$ edges is at least $m∕6$ except for two graphs of order 5 and 6.     

On the metric dimension of incidence graphs

A resolving set for a graph $\Gamma$ is a collection of vertices $S$, chosen so that for each vertex $v$, the list of distances from $v$ to the members of $S$ uniquely specifies $v$. The metric dimension$\mu \left(\Gamma \right)$ is the smallest size of a resolving set for $\Gamma$. We consider the metric dimension of two families of incidence graphs: incidence graphs of symmetric designs, and incidence graphs of symmetric transversal designs (i.e. symmetric nets). These graphs are the bipartite distance-regular graphs of diameter 3, and the bipartite, antipodal distance-regular graphs of diameter 4, respectively. In each case, we use the probabilistic method in the manner used by Babai to obtain bounds on the metric dimension of strongly regular graphs, and are able to show that $\mu \left(\Gamma \right)=O(\sqrt{n}logn)$ (where $n$ is the number of vertices).     

Maximality of the signless Laplacian energy

We study the problem of determining the graph with $n$ vertices having largest signless Laplacian energy. We conjecture it is the complete split graph whose independent set has (roughly) $2n∕3$ vertices. We show that the conjecture is true for several classes of graphs. In particular, the conjecture holds for the set of all complete split graphs of order $n$, for trees, for unicyclic and bicyclic graphs. We also give conditions on the number of edges, number of cycles and number of small eigenvalues so the graph satisfies the conjecture.     

Forcing faces in plane bipartite graphs (II)

The concept of forcing faces of a plane bipartite graph was first introduced in Che and Chen (2008) [3] [Z. Che, Z. Chen, Forcing faces in plane bipartite graphs, Discrete Mathematics 308 (2008) 2427–2439], which is a natural generalization of the concept of forcing hexagons of a hexagonal system introduced in Che and Chen (2006) [2] [Z. Che and Z. Chen, Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (2006) 649–668]. In this paper, we further extend this concept from finite faces to all faces (including the infinite face) as follows: A face $s$ (finite or infinite) of a 2-connected plane bipartite graph $G$ is called a forcing face if the subgraph $G?V\left(s\right)$ obtained by removing all vertices of $s$ together with their incident edges has exactly one perfect matching.For a plane elementary bipartite graph $G$ with more than two vertices, we give three necessary and sufficient conditions for $G$ to have all faces forcing. We also give a new necessary and sufficient condition for a finite face of $G$ to be forcing in terms of bridges in the $Z$-transformation graph $Z\left(G\right)$ of $G$. Moreover, for the graphs $G$ whose faces are all forcing, we obtain a characterization of forcing edges in $G$ by using the notion of $handle$, from which a simple counting formula for the number of forcing edges follows.     

Histories in Path Graphs

For a given graph G and a positive integer r the r-path graph, $P_r(G)$, has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length $r-1$, and their union forms either a cycle or a path of length $r+1$ in G. Let $P_r^k(G)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_r^k(G)$. The k-history $P_r^{-k}(H)$ is a subgraph of G that is induced by all edges that take part in the recursive definition of H. We present some general properties of k-histories and give a complete characterization of graphs that are k-histories of vertices of 2-path graph operator.     

On the fixing sets of dihedral groups

The fixing number of a graph $\Gamma$ is the minimum number of labeled vertices that, when fixed, remove all nontrivial automorphisms from the automorphism group of $\Gamma$. The fixing set of a finite group $G$ is the set of all fixing numbers of graphs whose automorphism groups are isomorphic to $G$. Previously, authors have studied the fixing sets of both abelian groups and symmetric groups. In this article, we determine the fixing set of the dihedral group.     

New characterizations of Gallai’s i-triangulated graphs

The i-triangulated graphs, introduced by Tibor Gallai in the early 1960s, have a number of characterizations—one of the simplest is that every odd cycle of length $5$ or more has noncrossing chords. A variety of new characterizations are proved, starting with a simple forbidden induced subgraph characterization and including the following two:(1) Every 2-connected induced subgraph $H$ is bipartite or chordal or, for every induced even cycle $C$ of $H$, the intersection of the neighborhoods in $H$ of all the vertices of $C$ induces a complete multipartite subgraph.(2) For every 2-connected induced subgraph $H$ that is not bipartite, every cardinality-2 minimal vertex separator of $H$ induces an edge.     

Doppelgangers and Lemke graphs

Let $G$ be a connected graph. A configuration of pebbles on $G$ is a function that assigns a nonnegative integer to each vertex. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if after making pebbling moves any vertex can get at least one pebble. The pebbling number of $G$, denoted $\pi \left(G\right)$, is the smallest integer such that any configuration of $\pi \left(G\right)$ pebbles on $G$ is solvable. A graph has the two-pebbling property if after placing more than $2\pi \left(G\right)?q$ pebbles on $G$, where $q$ is the number of vertices with pebbles, there is a sequence of pebbling moves so that at least two pebbles can be placed on any vertex. A graph without the two-pebbling property is called a Lemke graph. Previously, an infinite family of Lemke graphs was shown to exist by subdividing edges of the original Lemke graph. In this paper, we introduce a new way to create infinite families of Lemke graphs based on adding vertices as well as subdividing edges. We also characterize the configurations that violate the two-pebbling property on these graphs and conjecture another infinite family of Lemke graphs that generalizes the original Lemke graph.     

On 1-uniqueness and dense critical graphs for tree-depth

The tree-depth of $G$ is the smallest value of $k$ for which a labeling of the vertices of $G$ with elements from $\{1,\dots ,k\}$ exists such that any path joining two vertices with the same label contains a vertex having a higher label. The graph $G$ is $k$-critical if it has tree-depth $k$ and every proper minor of $G$ has smaller tree-depth.Motivated by a conjecture on the maximum degree of $k$-critical graphs, we consider the property of 1-uniqueness, wherein any vertex of a critical graph can be the unique vertex receiving label 1 in an optimal labeling. Contrary to an earlier conjecture, we construct examples of critical graphs that are not 1-unique and show that 1-unique graphs can have arbitrarily many more edges than certain critical spanning subgraphs. We also show that $(n?1)$-critical graphs on $n$ vertices are 1-unique and use 1-uniqueness to show that the Andrásfai graphs are critical with respect to tree-depth.     

Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs

Homomorphisms to a given graph $H$ ($H$-colourings) are considered in the literature among other graph colouring concepts. We restrict our attention to a special class of $H$-colourings, namely $H$ is assumed to be a star. Our additional requirement is that the set of vertices of a graph $G$ mapped into the central vertex of the star and any other colour class induce in $G$ an acyclic subgraph. We investigate the existence of such a homomorphism to a star of given order. The complexity of this problem is studied. Moreover, the smallest order of a star for which a homomorphism of a given graph $G$ with desired features exists is considered. Some exact values and many bounds of this number for chordal bipartite graphs, cylinders, grids, in particular hypercubes, are given. As an application of these results, we obtain some bounds on the cardinality of the minimum feedback vertex set for specified graph classes.     

The Chen–Chvátal conjecture for metric spaces induced by distance-hereditary graphs

A classical theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal conjectured a generalization of this result to arbitrary finite metric spaces, with a particular definition of lines in a metric space. We prove it for metric spaces induced by connected distance-hereditary graphs—a graph $G$ is called distance-hereditary if the distance between two vertices $u$ and $v$ in any connected induced subgraph $H$ of $G$ is equal to the distance between $u$ and $v$ in $G$.     

Randomly Pk-decomposable graphs

A graph $G$ is $H$-decomposable if it can be expressed as an edge-disjoint union of subgraphs, each subgraph isomorphic to $H$. If $G$ has the additional property that every $H$-decomposable subgraph of $G$ is part of an $H$-decomposition of $G$, then $G$ is randomly $H$-decomposable. Using computer assistance, we provide in this paper a characterization of randomly path-decomposable graphs for paths of length 11 or less. We also prove the following two results: (1) With one small exception, randomly $P_k$-decomposable graphs with a vertex of odd degree do not contain a $P_{k+1}$-subgraph, (2) When the edges of a $P_k$-subgraph are deleted from a connected randomly $P_k$-decomposable graph, the resulting graph has at most one nontrivial component.     

Flow-contractible configurations and group connectivity of signed graphs

Jaeger, Linial, Payan and Tarsi (JCTB, 1992) introduced the concept of group connectivity as a generalization of nowhere-zero flow for graphs. In this paper, we introduce group connectivity for signed graphs and establish some fundamental properties. For a finite abelian group $A$, it is proved that an $A$-connected signed graph is a contractible configuration for $A$-flow problem of signed graphs. In addition, we give sufficient edge connectivity conditions for signed graphs to be $A$-connected and study the group connectivity of some families of signed graphs.